你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
数据范围：1 <= K <= 100 1 <= N <= 10000
示例 1:1
2
3
4
5
6
7输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
示例 2:1
2输入：K = 2, N = 6
输出：3
示例 3:1
2输入：K = 3, N = 14
输出：4
题解：
考虑动态规划，我们用 dp[K][N] 表示有 K 个鸡蛋、N 层楼的状态下所需要的最少步数。当我们把一个鸡蛋从第 X 层楼扔下后，会有两种可能的结果：
- 鸡蛋没碎，那么我们还是有
K个鸡蛋，但答案只可能在第X层以上了，也就是说楼层数变为了N-X，接下来需要的最少步数为dp[K][N-X] - 鸡蛋碎了，那么我们只剩下
K-1个鸡蛋了，答案被锁定在下面的X-1层楼种，故接下来需要的最少步数为dp[K-1][X-1]
因为我们需要考虑的是在最坏情况下所需的步数，所以取二者的最大值作为从第 X 层楼扔下后需要的最少步数。然后，为了让最坏情况下需要的步数最少，我们需要确定究竟哪一个 X 的取值能够使得这个最大值最小。综上，我们可以列出状态转移方程如下：
有了转移方程，我们就可以求解每个状态的 dp 值了，代码如下：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
29int superEggDrop(int K, int N)
{
int dp[K+1][N+1]; //存放 superEggDrop(i, j)
int i, j, p, times;
for(i = 1; i <= K; ++i)
{
dp[i][0] = 0;
dp[i][1] = 1;
}
for(j = 1; j <= N; ++j)
{
dp[0][j] = 0;
dp[1][j] = j;
}
for(i = 2; i <= K; ++i)
for(j = 2; j <= N; ++j)
{
// 计算 superEggDrop(i, j)，存入 dp[i][j]
dp[i][j] = -1;
for(p = 1; p <= j; ++p)
{
// 从第 p 层扔
times = 1 + max(dp[i-1][p-1], dp[i][j-p]);
if(dp[i][j] == -1 || times < dp[i][j])
dp[i][j] = times;
}
}
return dp[K][N];
}
考虑一下时间复杂度，一共 $O(KN)$ 种状态，每种状态需要枚举 X，耗时为 $O(N)$，因此时间复杂度为 $O(KN^2)$，显然会超时，因此我们需要优化时间复杂度。
状态数不好优化，那么我们就优化求解每种状态即确定 X 取值的时间复杂度。我们发现，dp[K][N] 是关于 N 的增函数，于是有：
dp[K][N-X]随X增加单调递减dp[K-1][X-1]随X增加单调递增
而我们要找的是使得 dp[K][N-X] 和 dp[K-1][X-1] 的最大值最小的 X 的取值，显然，上述两个函数相交即 dp[K][N-X] = dp[K-1][X-1] 时，它们的最大值最小，交点对应的 X 的取值就是我们要找的 X。
通过以上对单调性的分析，我们就可以通过二分查找找到那个使得 dp[K][N-X] <= dp[K-1][X-1] 的 X 的最小取值。这样，我们就把时间复杂度优化到了 $O(KN\log N)$，可成功通过此题。代码如下：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
37int superEggDrop(int K, int N)
{
int dp[K+1][N+1]; //存放 superEggDrop(i, j)
int i, j;
for(i = 1; i <= K; ++i)
{
dp[i][0] = 0;
dp[i][1] = 1;
}
for(j = 1; j <= N; ++j)
{
dp[0][j] = 0;
dp[1][j] = j;
}
for(i = 2; i <= K; ++i)
for(j = 2; j <= N; ++j)
{
/*
二分查找使得 dp[i-1][p-1] >= dp[i][j-p] 的 p 的最小取值，
则 dp[i][j] = min(
max(dp[i-1][p-1], dp[i][j-p]),
max(dp[i-1][p-2], dp[i][j-p+1])
) + 1
*/
int l = 1, r = j, mid;
while(l < r)
{
mid = (l+r) / 2;
if(dp[i-1][mid-1] >= dp[i][j-mid])
r = mid;
else
l = mid + 1;
}
dp[i][j] = 1 + min(max(dp[i-1][l-1], dp[i][j-l]), max(dp[i-1][l-2], dp[i][j-l+1]));
}
return dp[K][N];
}