企业官网建设流程全解析

LeetCode 887 鸡蛋掉落（Super Egg Drop）题解：从暴力递归到逆向 DP 的完整推演

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本文是对 LeetCode 887「鸡蛋掉落（Super Egg Drop）」的深度题解，源自本仓库 problems/887.super-egg-drop.md，并在原题解基础上结合仓库中的动态规划专题 thinkings/dynamic-programming.md 与二分专题 thinkings/binary-search-1.md 进行扩展。阅读完本文，你将掌握从暴力递归、记忆化递归、bottom-up 动态规划，到「逆向思维 + 二分法」四层递进的完整解题脉络，理解为什么不同的状态转移方程性能差异巨大，并拿到 Python、C++、Java、JavaScript 四种语言的 AC 代码与复杂度分析。该题是公认难度较大的 hard 题之一，也是 vivo 2020 年提前批笔试原题，非常适合作为动态规划进阶训练的经典案例。

题目描述

你将获得 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

从仓库目录结构可以看到，本仓库将大量题解与思路图沉淀为独立文件，其中 assets/problems/887.super-egg-drop-1.png 直观还原了「0 层地面 + 1..N 楼层」的物理场景，方便在推导前建立直觉。

前置知识

• 递归
• 动态规划（本仓库的 thinkings/dynamic-programming.md 从记忆化递归逐步讲解到动态规划，是理解本文第三、四节递进关系的最佳前置读物；该文档明确提出「动态规划可以看成是填充函数这个黑盒」，本文正是这一思想的完整实践）

思路一：暴力递归（先打开思路）

这道题乍一看很复杂，我们不妨从几个简单的例子入手。

为了方便描述，用f(i, j)表示有 i 个鸡蛋、j 层楼时，在最坏情况下需要的最少移动次数。

假如有 2 个鸡蛋、6 层楼，我们应该先从哪层楼开始扔呢？想了一会，没有什么好的办法，那我们就考虑使用暴力的手段：既然不知道先从哪层楼开始扔是最优的，就依次模拟从第 1、第 2……第 6 层扔。每一层楼丢鸡蛋，都有两种可能：碎或者不碎。由于要求的是最坏情况，因此需要模拟两种情况，并取两种结果中移动次数的较大值（较大值就是最坏情况）。然后从六种扔法中选择最少次数的即可。

每一次选择从第几层楼扔之后，剩下的问题似乎是一个规模变小的同样问题。比如选择从 i 楼扔：

• 如果碎了，我们需要的答案就是1 + f(k - 1, i - 1)；
• 如果没有碎，需要在[i + 1, n]中继续找，这其实等价于在[1, n - i]中找。

可以发现问题被转化为规模更小的子问题，因此不难想到用递归来解决。伪代码如下：

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。

接下来，增加两行递归终止条件，这道题的暴力版就完成了：

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。

思路二：记忆化递归（优化但仍易挂）

把递归改造成记忆化递归，用缓存避免重复计算子问题：

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

性能比刚才稍微好一点，但状态依然是O(K * N)个、每个状态内部还要枚举 O(N) 个楼层，总体仍然很容易超时。

这与 thinkings/dynamic-programming.md 中「记忆化递归 = 查表的递归」的观点完全对应：递归函数参数(K, N)就是定义域，返回值就是值域，@lru_cache本质上就是一张自顶向下填充的 dp 表。

思路三：bottom-up 动态规划（正向 DP 仍不够）

既然递归是自顶向下，那我们改用迭代的 bottom-up 方式，用表来模拟所有情况，减少栈开销。我们知道所有情况无非是 N 和 K 的所有组合，枚举组合当然就是套两层循环。

你将dp[i][j]看成superEggDrop(i, j)，与递归是完全一一对应的。第一种写法的迭代代码：

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]

值得注意的是，这里内外循环的顺序无关紧要，复杂度也类似，各位可以随意调整内外循环的顺序。比如这样也可以：

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]

但这样还是不能 AC。这正是这道题困难的地方：一道题目往往有不止一种状态转移方程，而不同的状态转移方程往往性能是不同的。

思路四：把思路逆转——用「次数」换「楼层」（正解）

既然正向 DP 在「鸡蛋 × 楼层」的二维空间里打转，我们不妨把思路逆转：不再问「给定鸡蛋和楼层，最少扔几次」，而是问「给定鸡蛋数和扔的次数，最多能检测多少层楼」。

假设有一个函数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，因此时间复杂度相对可控。这么做的好处就是不用思考从哪里开始扔、扔完之后下一次从哪里扔。

对于这种二段性的题目应该想到二分法——本仓库的二分专题 thinkings/binary-search-1.md 指出，搜索类题目第一步要明确解空间，这里 m 的解空间就是[1, N]，且f(m, k)关于 m 单调不减（二段性），因此可以用二分在解空间内快速定位最小可行 m。实际上不二分也完全可以通过本题，下文会分别给出带二分和不带二分的实现。

f 函数的状态转移

最后剩下一个问题：这个神奇的 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, k) = f(m - 1, k - 1) + f(m - 1, k) + 1

边界条件：f(0, k) = 0（0 次扔不出结果）、f(m, 0) = 0（没有鸡蛋扔不出结果）。

仓库中的 assets/problems/887.super-egg-drop-2.png 正是这张dp[m][k]状态转移表的可视化：行代表扔鸡蛋次数 m（0~6），列代表鸡蛋数量 k，表内数值即为「k 个鸡蛋扔 m 次能达到的最大楼层数」，并用箭头标出了dp[m-1][k-1]与dp[m-1][k]两个来源状态，与上述转移方程完全一致。

带二分的实现

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

代码（多语言实现）

以下为不带二分的最终版本，直接逐次递增 m，一旦dp[k][m] >= N即可返回。代码支持：Python, C++, Java, JavaScript。

Python:

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:

#include <vector> #include <functional> class Solution { public: int superEggDrop(int K, int N) { std::vector<std::vector<int>> dp(K + 1, std::vector<int>(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:

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:

/** * @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)$

对比思路一/三的正向 DP：状态数同样是O(K * N)，但正向 DP 每个状态内部还要再枚举一次楼层（第 k 层扔），整体达到O(K * N^2)；而逆向 DP 的转移是 O(1) 加法，配合dp[k][m] >= N的提前返回与二分的二段性剪枝，性能量级完全不同。这直观印证了原题解的核心论断：状态转移方程的选择决定算法性能。

总结

• 对于困难题，先举几个简单例子帮助你思考，比如本题先手算 K=1、K=2 的小规模情形。
• 递归和迭代的关系，以及如何从容地在两者间穿梭：递归用函数调用模拟所有情况，动态规划用表模拟所有情况，二者本质相同，可相互改写。
• 如果你还不熟悉动态规划，可以先从递归做起，多画图（可以参考仓库中的 assets/drawio/egg-drop.drawio 流程图）；当你做多了题之后，就会越来越从容。
• 对于动态规划问题，往往有不止一种状态转移方程，而不同的状态转移方程往往性能是不同的——正向枚举「在哪层扔」与逆向枚举「扔 m 次能覆盖几层」，就是本题最典型的对照案例。
• 二段性题目要想到二分法：f(m, k)关于 m 单调不减，最小可行 m 完全可以用二分在[1, N]内快速定位。

本题在仓库中被收录于 collections/hard.md 的困难题清单，并在 SUMMARY.md 与 README.md 中均有索引，可据此快速定位到仓库内的题解体系；该题也是 vivo 2020 年提前批笔试原题（同场还考察了合并 k 个链表、种花问题），实战价值高。友情提示：大家不要为了这个题目高空抛物哦。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode