leetcode 887.鸡蛋掉落（Super Egg Drop）c语言

编程入门行业动态更新时间:2024-10-21 18:49:53

leetcode 887.<a href=https://www.elefans.com/category/jswz/34/1710264.html style= 鸡蛋掉落（Super Egg Drop）c语言"/>

leetcode 887.鸡蛋掉落（Super Egg Drop）c语言

- 1.description
- 2.solution
- - 2.1 超时DP
  - 2.2 DP+二分优化
  - 2.3 换种思路

1.description

中文力扣中题意描述不够清楚，下面是leetcode原题：

You are given K eggs, and you have access to a building with N floors from 1 to N.

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.

Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).

Your goal is to know with certainty what the value of F is.

What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?

Example 1:

Input: K = 1, N = 2
Output: 2
Explanation: 
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.

Example 2:

Input: K = 2, N = 6
Output: 3

Example 3:

Input: K = 3, N = 14
Output: 4

Note:

1 <= K <= 100
1 <= N <= 10000

2.solution

一开始题意都不好理解，看了别人的思路明白了一点，属于典型的DP问题

2.1 超时DP

状态定义：dp[i] [j] 表示 i 层楼（不是高度，可理解为区间长度），使用 j 个鸡蛋的最少实验次数，因此dp[N] [K]即为题解。

说明：

i 表示的是楼层的大小，不是高度（第几层）的意思，例如楼层区间 [8, 9, 10] 的大小为 3。
j 表示可以使用的鸡蛋的个数，它是约束条件。

状态转移方程：

设指定的楼层为 k，k >= 1 且 k <= i：

如果鸡蛋破碎，测试 F 值的实验就得在 k 层以下做（不包括 k 层），这里已经使用了一个鸡蛋，因此测出 F 值的最少实验次数是：dp[k - 1] [j - 1]；

如果鸡蛋完好，测试 F 值的实验就得在 k 层以上做（不包括 k 层），这里这个鸡蛋还能使用，因此测出 F 值的最少实验次数是：dp[i - k] [j]，例如总共 8 层，在第 5 层扔下去没有破碎，则需要在 [6, 7, 8] 层继续做实验，因此区间的大小就是 8 - 5 = 3。

最坏情况下，是这两个子问题的较大者，由于在第 k 层扔下鸡蛋算作一次实验，k 的值在 [1, i]，对于每一个 k 都对应了一组值的最大值，取这些 k 下的最小值（最优子结构），因此：

d p [ i ] [ j ] = min ⁡ 1 ≤ k ≤ i ( max ⁡ ( d p [ k − 1 ] [ j − 1 ] , d p [ i − k ] [ j ] ) + 1 ) d p[i][j]=\min _{1 \leq k \leq i}(\max (d p[k-1][j-1], d p[i-k][j])+1) dp[i][j]=1≤k≤imin(max(dp[k−1][j−1],dp[i−k][j])+1)
初始化：

一般而言，需要 0 这个状态的值，这里 0 层楼和 0 个鸡蛋是需要考虑进去的，它们的值会被后来的值所参考，并且也比较容易得到。

因此表格需要 N + 1 行，K + 1 列。

由于 F 值不会超过最大楼层的高度，要求的是最小值，因此初始化的时候，可以叫表格的单元格值设置成一个很大的数，但是这个数肯定也不会超过当前考虑的楼层的高度。

static inline int min(int a, int b){return a < b ? a : b;
}static inline int max(int a, int b){return a > b ? a : b;
}int superEggDrop(int K, int N){// dp:(N+1)*(K+1), 0 个楼层和 0 个鸡蛋的情况都需要算上去，虽然没有实际的意义，但是作为递推的起点，被其它状态值所参考int **dp = (int**)malloc((N+1)*sizeof(int*));for(int i=0; i<N+1; ++i){dp[i] = (int*)malloc((K+1)*sizeof(int));}for(int i=0; i<N+1; ++i){for(int j=1; j<K+1; ++j){dp[i][j] = i;}}// 单独初始化第0列, 0个鸡蛋, 无法测试, 故为0for(int i=0; i<N+1; ++i){dp[i][0] = 0;}for(int i=2; i<N+1; ++i){for(int j=2; j<K+1; ++j){for(int k=1; k<=i; ++k){dp[i][j] = min(dp[i][j], max(dp[k-1][j-1], dp[i-k][j]) + 1);}}}return dp[N][K];
}

结果超时，时间复杂度：O(N^2K)

空间复杂度：O(NK)

2.2 DP+二分优化

「状态转移方程」里最外层的变量是 k，它枚举了扔下鸡蛋的楼层的高度，这里它是自变量，将其余的 i 和 j 视为常数：

dp[k - 1] [j - 1]：根据语义，k 增大的时候，楼层大小越大，它的值就越大；
dp[i - k] [j]：根据语义，k 增大的时候，楼层大小越小，它的值就越小。

可以发现 dp[k - 1] [j - 1] 单调不减，dp[i - k] [j] 单调不增，并且它们的值都是整数。因此，这里求得是一个“谷底”，可考虑用二分查找优化。

static inline int max(int a, int b){return a > b ? a : b;
}int superEggDrop(int K, int N){// dp:(N+1)*(K+1), 0 个楼层和 0 个鸡蛋的情况都需要算上去，虽然没有实际的意义，但是作为递推的起点，被其它状态值所参考int **dp = (int**)malloc((N+1)*sizeof(int*));for(int i=0; i<N+1; ++i){dp[i] = (int*)malloc((K+1)*sizeof(int));}for(int i=0; i<N+1; ++i){for(int j=1; j<K+1; ++j){dp[i][j] = i;}}// 单独初始化第0列, 0个鸡蛋, 无法测试, 故为0for(int i=0; i<N+1; ++i){dp[i][0] = 0;}for(int i=2; i<N+1; ++i){for(int j=2; j<K+1; ++j){int low = 1, high = i;while(low <= high){int mid = low + ((high - low)>>1);int val1 = dp[mid-1][j-1];int val2 = dp[i-mid][j];if (val1 > val2){if(mid == 1 || dp[mid-2][j-1] < dp[i-mid+1][j]){break;}high = mid - 1;}else if(val1 == val2){break;}else{low = mid + 1;}}int mid = low + ((high - low)>>1);dp[i][j] = dp[mid-1][j-1] + 1;}}return dp[N][K];
}

时间复杂度：O(NKlog N)

空间复杂度：O(NK)

执行用时：172 ms
内存消耗：37.7 MB

二分查找还可以优化，通过不断更新low的下限（low下限随着楼层N的增大也在增大）

2.3 换种思路

上述方法其实是蛮力解，换种思路：这里状态的定义有所不同，dp[k] [s] 表示用 k 个鸡蛋操作 s 步能够求解的最大楼层。

int superEggDrop(int K, int N){int **dp = (int**)malloc((K+1)*sizeof(int*));for(int i=0; i<K+1; ++i){dp[i] = (int*)malloc((N+1)*sizeof(int));memset(dp[i], 0, (N+1)*sizeof(int));}int step = 0;while(dp[K][step] < N){step++;for(int i=1; i<=K; ++i){// dp[k][s] means the number of floors we can detect with k eggs and s stepsdp[i][step] = dp[i][step-1] + dp[i-1][step-1] + 1;}}// freefor(int i=0; i<K+1; ++i){if(dp[i]){free(dp[i]);}}if(dp){free(dp);}return step;
}

时间复杂度：O(Klog N)

空间复杂度：O(NK)

执行用时：4 ms

内存消耗：26.9 MB

dp表可进一步缩减为一维，空间复杂度进一步减小：

int superEggDrop(int K, int N){int *dp = (int*)malloc((K+1)*sizeof(int));memset(dp, 0, (K+1)*sizeof(int));int step = 0;while(dp[K] < N){step++;for(int i=K; i>=1; --i){dp[i] = dp[i] + dp[i-1] + 1;}}// freeif(dp){free(dp);}return step;
}

时间复杂度：O(Klog N)

空间复杂度：O(K)