# 0887. 鸡蛋掉落 ### 题目地址(887. 鸡蛋掉落) ### 题目描述 ``` 你将获得  K  个鸡蛋，并可以使用一栋从  1  到  N   共有 N  层楼的建筑。 每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。 你知道存在楼层  F ，满足  0 <= F <= N 任何从高于 F  的楼层落下的鸡蛋都会碎，从  F  楼层或比它低的楼层落下的鸡蛋都不会破。 每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层  X  扔下（满足  1 <= X <= N）。 你的目标是确切地知道 F 的值是多少。 无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？ 示例 1： 输入：K = 1, N = 2 输出：2 解释： 鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。 否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。 如果它没碎，那么我们肯定知道 F = 2 。 因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。 示例 2： 输入：K = 2, N = 6 输出：3 示例 3： 输入：K = 3, N = 14 输出：4 提示： 1 <= K <= 100 1 <= N <= 10000 ``` ### 前置知识 * 递归 * [动态规划](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/dynamic-programming) ### 思路 本题也是 vivo 2020 年提前批的一个笔试题。时间一个小时，一共三道题，分别是本题，合并 k 个链表，以及种花问题。 这道题我在很早的时候做过，也写了题解。现在看来，思路没有讲清楚。没有讲当时的思考过程还原出来，导致大家看的不太明白。今天给大家带来的是 887.super-egg-drop 题解的**重制版**。思路更清晰，讲解更透彻，如果觉得有用，那就转发在看支持一下？OK，我们来看下这道题吧。 这道题乍一看很复杂，我们不妨从几个简单的例子入手，尝试打开思路。 为了方便描述，我将 f(i, j) 表示有 i 个鸡蛋， j 层楼，在最坏情况下，最少的次数。 假如有 2 个鸡蛋，6 层楼。 我们应该先从哪层楼开始扔呢？想了一会，没有什么好的办法。我们来考虑使用暴力的手段。 既然我不知道先从哪层楼开始扔是最优的，那我就依次模拟从第 1，第 2。。。第 6 层扔。每一层楼丢鸡蛋，都有两种可能，碎或者不碎。由于是最坏的情况，因此我们需要模拟两种情况，并取两种情况中的扔次数的较大值（较大值就是最坏情况）。 然后我们从六种扔法中选择最少次数的即可。 ![](https://p.ipic.vip/5vz4r2.jpg) （图1） 而每一次选择从第几层楼扔之后，剩下的问题似乎是一个规模变小的同样问题。比如选择从 i 楼扔，如果碎了，我们需要的答案就是 1 + f(k-1, i-1)，如果没有碎，需要在找 \[i+1, n]，这其实等价于在 \[1,n-i]中找。我们发现可以将问题转化为规模更小的子问题，因此不难想到递归来解决。 伪代码： ```py def superEggDrop(K, N): ans = N # 暴力枚举从第 i 层开始扔 for i in range(1, N + 1): ans = min(ans, max(self.superEggDrop(K - 1, i - 1) + 1, self.superEggDrop(K, N - i) + 1)) return ans ``` 如上代码： * self.superEggDrop(K - 1, i - 1) 指的是鸡蛋破碎的情况，我们就只剩下 K - 1 个鸡蛋， 并且 i - 1 个楼层需要 check。 * self.superEggDrop(K, N - i) + 1 指的是鸡蛋没有破碎的情况，我们仍然有 K 个鸡蛋， 并且剩下 N - i 个楼层需要 check。 接下来，我们增加两行递归的终止条件，这道题就完成了。 ```py class Solution: def superEggDrop(self, K: int, N: int) -> int: if K == 1: return N if N == 0 or N == 1: return N ans = N # 暴力枚举从第 i 层开始扔 for i in range(1, N + 1): ans = min(ans, max(self.superEggDrop(K - 1, i - 1) + 1, self.superEggDrop(K, N - i) + 1)) return ans ``` 可是如何这就结束的话，这道题也不能是 hard，而且这道题是公认难度较大的 hard 之一，肯定不会被这么轻松解决。 实际上上面的代码会 TLE，我们尝试使用记忆化递归来试一下，看能不能 AC。 ```py class Solution: @lru_cache() def superEggDrop(self, K: int, N: int) -> int: if K == 1: return N if N == 0 or N == 1: return N ans = N # 暴力枚举从第 i 层开始扔 for i in range(1, N + 1): ans = min(ans, max(self.superEggDrop(K - 1, i - 1) + 1, self.superEggDrop(K, N - i) + 1)) return ans ``` 性能比刚才稍微好一点，但是还是很容易挂。 那只好 bottom-up（动态规划）啦。 ![](https://p.ipic.vip/gnmqq1.jpg) (图 2) 我将上面的过程简写成如下形式： ![](https://p.ipic.vip/m4ruew.jpg) (图 3) 与其递归地进行这个过程，我们可以使用迭代的方式。 相比于上面的递归式，减少了栈开销。然而两者有着很多的相似之处。 如果说递归是用函数调用来模拟所有情况， 那么动态规划就是用表来模拟。我们知道所有的情况，无非就是 N 和 K 的所有组合，我们怎么去枚举 K 和 N 的所有组合？ 当然是套两层循环啦！ ![](https://p.ipic.vip/o91aox.jpg) （图 4. 递归 vs 迭代） 如上，你将 dp\[i]\[j] 看成 superEggDrop(i, j)，是不是和递归是一摸一样？ 来看下迭代的代码： ```py class Solution: def superEggDrop(self, K: int, N: int) -> int: dp = [[i for _ in range(K+1)] for i in range(N + 1)] for i in range(N + 1): for j in range(1, K + 1): dp[i][j] = i if j == 1: continue if i == 1 or i == 0: break for k in range(1, i + 1): dp[i][j] = min(dp[i][j], max(dp[k - 1][j-1] + 1, dp[i-k][j] + 1)) return dp[N][K] ``` 值得注意的是，在这里内外循环的顺序无关紧要，并且内外循坏的顺序对我们写代码来说复杂程度也是类似的，各位客官可以随意调整内外循环的顺序。比如这样也是可以的： ```py class Solution: def superEggDrop(self, K: int, N: int) -> int: dp = [[i for i in range(N+1)] for _ in range(K + 1)] for i in range(1, K + 1): for j in range(N + 1): dp[i][j] = j if i == 1: break if j == 1 or j == 0: continue for k in range(1, j + 1): dp[i][j] = min(dp[i][j], max(dp[i - 1][k - 1] + 1, dp[i][j - k] + 1)) return dp[K][N] ``` 总结一下，上面的解题方法思路是： ![](https://p.ipic.vip/ynsszu.jpg) (图 5) 然而这样还是不能 AC。这正是这道题困难的地方。 **一道题目往往有不止一种状态转移方程，而不同的状态转移方程往往性能是不同的。** 那么这道题有没有性能更好的其他的状态转移方程呢？ 把思路逆转！ ![](https://p.ipic.vip/jtgl7i.jpg) (图 6) > 这是《逆转裁判》 中经典的台词， 主角在深处绝境的时候，会突然冒出这句话，从而逆转思维，寻求突破口。 我们这样来思考这个问题。 既然题目要求最少的扔的次数，假设有一个函数 f(k, i)，他的功能是求出 k 个鸡蛋，扔 i 次所能检测的最高楼层。 我们只需要不断进行发问： * ”f 函数啊 f 函数，我扔一次可以么？“， 也就是判断 f(k, 1) >= N 的返回值 * ”f 函数啊 f 函数，我扔两次呢？“， 也就是判断 f(k, 2) >= N 的返回值 * ... * ”f 函数啊 f 函数，我扔 m 次呢？“， 也就是判断 f(k, m) >= N 的返回值 我们只需要返回第一个返回值为 true 的 m 即可。由于 m 不会大于 N，因此时间复杂度也相对可控。这么做的好处就是不用思考从哪里开始扔，扔完之后下一次从哪里扔。 对于这种二段性的题目应该想到二分法，如果你没想起来，请先观看我的仓库里的二分专题哦。实际上不二分也完全可以通过此题目，具体下方代码，有实现带二分的和不带二分的。 最后剩下一个问题。这个神奇的 f 函数怎么实现呢？ * 摔碎的情况，可以检测的最大楼层数是`f(m - 1, k - 1)`。也就是说，接下来我们需要往下找，最多可以找 f(m-1, k-1) 层 * 没有摔碎的情况，可以检测的最大楼层数是`f(m - 1, k)`。也就是说，接下来我们需要往上找，最多可以找 f(m-1, k) 层 也就是当前扔的位置上面可以有 f(m-1, k) 层，下面可以有 f(m-1, k-1) 层，这样无论鸡蛋碎不碎，我都可以检测出来。因此能检测的最大楼层数就是**向上找的最大楼层数+向下找的最大楼层数+1**，其中 1 表示当前层，即 `f(m - 1, k - 1) + f(m - 1, k) + 1` 首先我们来看下二分代码： ```py class Solution: def superEggDrop(self, K: int, N: int) -> int: @cache def f(m, k): if k == 0 or m == 0: return 0 return f(m - 1, k - 1) + 1 + f(m - 1, k) l, r = 1, N while l <= r: mid = (l + r) // 2 if f(mid, K) >= N: r = mid - 1 else: l = mid + 1 return l ``` 下面代码区我们实现不带二分的版本。 ### 代码 代码支持：Python, CPP, Java, JavaSCript Python: ```py class Solution: def superEggDrop(self, K: int, N: int) -> int: dp = [[0] * (N + 1) for _ in range(K + 1)] for m in range(1, N + 1): for k in range(1, K + 1): dp[k][m] = dp[k - 1][m - 1] + 1 + dp[k][m - 1] if dp[k][m] >= N: return m return N # Fallback, should not reach here ``` CPP: ```cpp #include #include class Solution { public: int superEggDrop(int K, int N) { std::vector> dp(K + 1, std::vector(N + 1, 0)); for (int m = 1; m <= N; ++m) { for (int k = 1; k <= K; ++k) { dp[k][m] = dp[k - 1][m - 1] + 1 + dp[k][m - 1]; if (dp[k][m] >= N) { return m; } } } return N; // Fallback, should not reach here } }; ``` Java: ```java import java.util.Arrays; class Solution { public int superEggDrop(int K, int N) { int[][] dp = new int[K + 1][N + 1]; for (int m = 1; m <= N; ++m) { for (int k = 1; k <= K; ++k) { dp[k][m] = dp[k - 1][m - 1] + 1 + dp[k][m - 1]; if (dp[k][m] >= N) { return m; } } } return N; // Fallback, should not reach here } } ``` JavaSCript: ```js /** * @param {number} k * @param {number} n * @return {number} */ var superEggDrop = function superEggDrop(K, N) { const dp = Array.from({ length: K + 1 }, () => Array(N + 1).fill(0)); for (let m = 1; m <= N; ++m) { for (let k = 1; k <= K; ++k) { dp[k][m] = dp[k - 1][m - 1] + 1 + dp[k][m - 1]; if (dp[k][m] >= N) { return m; } } } return N; // Fallback, should not reach here } ``` **复杂度分析** * 时间复杂度：$O(N \* K)$ * 空间复杂度：$O(N \* K)$ 对为什么用加法的同学有疑问的可以看我写的[《对《丢鸡蛋问题》的一点补充》](https://lucifer.ren/blog/2020/08/30/887.super-egg-drop-extension/)。 ### 总结 * 对于困难，先举几个简单例子帮助你思考。 * 递归和迭代的关系，以及如何从容地在两者间穿梭。 * 如果你还不熟悉动态规划，可以先从递归做起。多画图，当你做多了题之后，就会越来越从容。 * 对于动态规划问题，往往有不止一种状态转移方程，而不同的状态转移方程往往性能是不同的。 > 友情提示: 大家不要为了这个题目高空抛物哦。 更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》获取更多更新鲜的 LeetCode 题解 ![](https://p.ipic.vip/ln4btk.jpg) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/887.super-egg-drop.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.