1. 问题
给了K个蛋，总共有N层楼。而鸡蛋会在F层以上碎掉。
无论F值是多少，你需要确定F值，而确定这个值，需要试验的至少多少次？
例子：
1
2
3
4
5
6
7
输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少
2. 解答思路
经典的动态规划题，需要重点标记！！
Google经典面试题，动态规划：
- 定义状态：
dp(k, n)总共n层楼（不是高度），k个蛋，需要的实验次数 - 很容易得到转移方程
dp(k, n) = 1 + min(max(dp(k, n-i), dp(k-1, i-1)))，其中max内的是- 前一项：鸡蛋在
i层没有碎，所以只需要往上找，剩余楼层n-i层 - 后一项：鸡蛋在
i层碎了，所以需要向下找，剩余楼层i-1（不含i）
- 前一项：鸡蛋在
- 暴力求解需要$O(KN^2)$，会超时
- 优化：
dp(k, n-i)单调递减，dp(k-1,i-1)单调递增，所以利用二分法找交点即可，时间复杂度降低为$O(KNlog(N))$，二分法如下： - 确定要二分的范围为[1, n]- 由于dp(k, n-i)递减，dp(k-1, i-1)递增，所以两者之差递减 - 二分搜索时作差 - 若差值大于0，则需要向前查找，start += 1- 若差值小于0，则需要向后查找，end -= 1- 若等于0，就是答案，退出- 由于可能不会出现等于0的情况，为了保险，可以每次搜索时都计算一下转移方程，取一下最小值
3. 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public int superEggDrop(int K, int N) {
int[][] dp = new int[K + 1][N + 1];
for(int i = 0; i <= K; i++) {
Arrays.fill(dp[i], 100000);
}
for(int i = 0; i <= K; i++) {
dp[i][0] = 0;
}
for(int i = 1; i <= K; i++) {
for(int j = 1; j <= N; j++) {
// 线性搜索
/* for(int k = 1; k <= j; k++) {
dp[i][j] = Math.min(Math.max(dp[i][j - k], dp[i - 1][k - 1]) + 1,
dp[i][j]);
} */
// 二分搜索，利用函数单调性
// diff = dp[i][j - k] - dp[i - 1][k - 1];
// k from [1, j]
// get diff => 0 or closest to 0 using binary search on k
int start = 1;
int end = j;
while(start <= end) {
int mid = (start + end) / 2;
int val = dp[i][j - mid] - dp[i - 1][mid - 1];
// 为了保险每次调用转移方程求最小值
dp[i][j] = Math.min(dp[i][j],
Math.max(dp[i][j - mid], dp[i - 1][mid - 1]) + 1);
if(val > 0) {
start = mid + 1;
} else if(val == 0) {
break;
} else {
end = mid - 1;
}
}
}
}
return dp[K][N];
}
}
