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 Fwill break, and any egg dropped at or below floor Fwill 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 <= 1001 <= N <= 10000
这道题说给了我们K个鸡蛋，还有一栋共N层的大楼，说是鸡蛋有个临界点的层数F，高于这个层数扔鸡蛋就会碎，否则就不会，问我们找到这个临界点最小需要多少操作，注意这里的操作只有当前还有没碎的鸡蛋才能进行。这道题是基于经典的扔鸡蛋的问题改编的，原题是有 100 层楼，为了测鸡蛋会碎的临街点，最少可以扔几次？答案是只用扔 14 次就可以测出来了，讲解可以参见油管上的这个视频，这两道题看着很相似，其实是有不同的。这道题限制了鸡蛋的个数K，假设我们只有1个鸡蛋，碎了就不能再用了，这时我们要测 100 楼的临界点的时候，只能一层一层去测，当某层鸡蛋碎了之后，就知道临界点了，所以最坏情况要测 100 次，注意要跟经典题目中扔 14 次要区分出来。那么假如有两个鸡蛋呢，其实需要的次数跟经典题目中的一样，都是 14 次，这是为啥呢？因为在经典题目中，我们是分别间隔 14，13，12，…，2，1，来扔鸡蛋的，当我们有两个鸡蛋的时候，我们也可以这么扔，第一个鸡蛋仍在 14 楼，若碎了，说明临界点一定在 14 楼以内，可以用第二个鸡蛋去一层一层的测试，所以最多操作 14 次。若第一个鸡蛋没碎，则下一次扔在第 27 楼，假如碎了，说明临界点在 (14,27] 范围内，用第二个鸡蛋去一层一层测，总次数最多 13 次。若第一个鸡蛋还没碎，则继续按照 39, 50, …, 95, 99，等层数去测，总次数也只可能越来越少，不会超过 14 次的。但是照这种思路分析的话，博主就不太清楚有3个鸡蛋，在 100 楼测，最少的步骤数，答案是9次，博主不太会分析怎么测的，各位看官大神知道的话一定要告诉博主啊。
其实这道题比较好的解法是用动态规划 Dynamic Programming，因为这里有两个变量，鸡蛋数K和楼层数N，所以就要使用一个二维数组 DP，其中 dp[i][j] 表示有i个鸡蛋，j层楼要测需要的最小操作数。那么我们在任意k层扔鸡蛋的时候就有两种情况（注意这里的k跟鸡蛋总数K没有任何关系，k的范围是 [1, j]）：
- 鸡蛋碎掉：接下来就要用 i-1 个鸡蛋来测 k-1 层，所以需要 dp[i-1][k-1] 次操作。
- 鸡蛋没碎：接下来还可以用i个鸡蛋来测 j-k 层，所以需要 dp[i][j-k] 次操作。
因为我们每次都要面对最坏的情况，所以在第j层扔，需要 max(dp[i-1][k-1], dp[i][j-k])+1 步，状态转移方程为：
dp[i][j] = min(dp[i][j], max(dp[i - 1][k - 1], dp[i][j - k]) + 1) ( 1 <= k <= j )
这种写法会超时 Time Limit Exceeded，代码请参见评论区1楼，OJ 对时间卡的还是蛮严格的，所以我们就需要想办法去优化时间复杂度。这种写法里面我们枚举了 [1, j] 范围所有的k值，总时间复杂度为 O(KN^2)，若我们仔细观察 dp[i - 1][k - 1] 和 dp[i][j - k]，可以发现前者是随着k递增，后者是随着k递减，且每次变化的值最多为1，所以只要存在某个k值使得二者相等，那么就能得到最优解，否则取最相近的两个k值做比较，由于这种单调性，我们可以在 [1, j] 范围内对k进行二分查找，找到第一个使得 dp[i - 1][k - 1] 不小于 dp[i][j - k] 的k值，然后用这个k值去更新 dp[i][j] 即可，这样时间复杂度就减少到了 O(KNlgN)，其实也是险过，参见代码如下：
解法一：
class Solution {
public:
int superEggDrop(int K, int N) {
vector<vector<int>> dp(K + 1, vector<int>(N + 1));
for (int j = 1; j <= N; ++j) dp[1][j] = j;
for (int i = 2; i <= K; ++i) {
for (int j = 1; j <= N; ++j) {
dp[i][j] = j;
int left = 1, right = j;
while (left < right) {
int mid = left + (right - left) / 2;
if (dp[i - 1][mid - 1] < dp[i][j - mid]) left = mid + 1;
else right = mid;
}
dp[i][j] = min(dp[i][j], max(dp[i - 1][right - 1], dp[i][j - right]) + 1);
}
}
return dp[K][N];
}
};
进一步来想，对于固定的k，dp[i][j-k] 会随着j的增加而增加，最优决策点也会随着j单调递增，所以在每次移动j后，从上一次的最优决策点的位置来继续向后查找最优点即可，这样时间复杂度就优化到了 O(KN)，我们使用一个变量s表示当前的j值下的的最优决策点，然后当j值改变了，我们用一个 while 循环，来找到第下一个最优决策点s，使得 dp[i - 1][s - 1] 不小于 dp[i][j - s]，参见代码如下：
解法二：
class Solution {
public:
int superEggDrop(int K, int N) {
vector<vector<int>> dp(K + 1, vector<int>(N + 1));
for (int j = 1; j <= N; ++j) dp[1][j] = j;
for (int i = 2; i <= K; ++i) {
int s = 1;
for (int j = 1; j <= N; ++j) {
dp[i][j] = j;
while (s < j && dp[i - 1][s - 1] < dp[i][j - s]) ++s;
dp[i][j] = min(dp[i][j], max(dp[i - 1][s - 1], dp[i][j - s]) + 1);
}
}
return dp[K][N];
}
};
其实我们还可以进一步优化时间复杂度到 O(KlgN)，不过就比较难想到了，需要将问题转化一下，变成已知鸡蛋个数，和操作次数，求最多能测多少层楼的临界点。还是使用动态规划 Dynamic Programming 来做，用一个二维 DP 数组，其中 dp[i][j] 表示当有i次操作，且有j个鸡蛋时能测出的最高的楼层数。再来考虑状态转移方程如何写，由于 dp[i][j] 表示的是在第i次移动且使用第j个鸡蛋测试第 dp[i-1][j-1]+1 层，因为上一个状态是第i-1次移动，且用第j-1个鸡蛋。此时还是有两种情况：
- 鸡蛋碎掉：说明至少可以测到的不会碎的层数就是 dp[i-1][j-1]。
- 鸡蛋没碎：那这个鸡蛋可以继续利用，此时我们还可以再向上查找 dp[i-1][j] 层。
那么加上当前层，总共可以通过i次操作和j个鸡蛋查找的层数范围是 [0, dp[i-1][j-1] + dp[i-1][j] + 1]，这样就可以得到状态转移方程如下：
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1
当 dp[i][K] 正好小于N的时候，i就是我们要求的最小次数了，参见代码如下：
解法三：
class Solution {
public:
int superEggDrop(int K, int N) {
vector<vector<int>> dp(N + 1, vector<int>(K + 1));
int m = 0;
while (dp[m][K] < N) {
++m;
for (int j = 1; j <= K; ++j) {
dp[m][j] = dp[m - 1][j - 1] + dp[m - 1][j] + 1;
}
}
return m;
}
};
我们可以进一步的优化空间，因为当前的操作次数值的更新只跟上一次操作次数有关，所以我们并不需要保存所有的次数，可以使用一个一维数组，其中 dp[i] 表示当前次数下使用i个鸡蛋可以测出的最高楼层。状态转移方程的推导思路还是跟上面一样，参见代码如下：
解法四：
class Solution {
public:
int superEggDrop(int K, int N) {
vector<int> dp(K + 1);
int res = 0;
for (; dp[K] < N; ++res) {
for (int i = K; i > 0; --i) {
dp[i] = dp[i] + dp[i - 1] + 1;
}
}
return res;
}
};
下面这种方法就非常的 tricky 了，居然推导出了使用k个鸡蛋，移动x次所能测的最大楼层数的通项公式，推导过程可以参见这个帖子，通项公式如下： f(k,x) = x(x-1)..(x-k)/k! + ... + x(x-1)(x-2)/3! + x(x-1)/2! + x 这数学功底也太好了吧，有了通向公式后，我们就可以通过二分搜索法 Binary Search 来快速查找满足题目的x。这里其实是博主之前总结贴 LeetCode Binary Search Summary 二分搜索法小结 中的第四类，用子函数当作判断关系，这里子函数就是用来实现上面的通向公式的，不过要判断，当累加和大于等于N的时候，就要把当的累加和返回，这样相当于进行了剪枝，因为在二分法中只需要知道其跟N的大小关系，并不 care 到底大了多少，这样快速定位x的方法运行速度貌似比上面的 DP 解法要快不少，但是这通项公式尼玛谁能容易的推导出来，只能膜拜叹服了，参见代码如下：
解法五：
class Solution {
public:
int superEggDrop(int K, int N) {
int left = 1, right = N;
while (left < right) {
int mid = left + (right - left) / 2;
if (helper(mid, K, N) < N) left = mid + 1;
else right = mid;
}
return right;
}
int helper(int x, int K, int N) {
int res = 0, r = 1;
for (int i = 1; i <= K; ++i) {
r *= x - i + 1;
r /= i;
res += r;
if (res >= N) break;
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/887
参考资料：
https://leetcode.com/problems/super-egg-drop/
https://www.cnblogs.com/Phantom01/p/9490508.html
https://www.acwing.com/solution/leetcode/content/579/
https://leetcode.com/problems/super-egg-drop/discuss/159508/easy-to-understand
https://leetcode.com/problems/super-egg-drop/discuss/299526/BinarySearch-or-Easiest-or-Explanation
https://leetcode.com/problems/super-egg-drop/discuss/158974/C%2B%2BJavaPython-2D-and-1D-DP-O(KlogN)
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
