LeetCode 887. 鸡蛋掉落
目录
题目描述
题意分析
楼里存在一个确定但未知的临界层
f，满足从高于f的楼层扔下鸡蛋必碎、从不高于f的楼层扔下必不碎，f的取值范围是0到n，共n + 1种可能。手上有k枚鸡蛋，碎掉的鸡蛋不能再用，没碎的可以反复用。要求的不是某一次运气好时的次数，而是最坏情况下的最少操作次数：策略必须保证无论真实的
f是哪一个值，都能在这么多次之内把它唯一确定下来。这是一个「先由我选楼层、再由对手挑最差结果」的极小化极大问题，所以每扔一次都必须同时为「碎」和「没碎」两条分支负责，不能只顾其中一条。约束信号很明确：
1 <= k <= 100，1 <= n <= 10^4。楼层数上万，说明与n相关的枚举不能套在状态里；而答案本身一定很小，k = 1时最坏也只要n次，k稍大时更是断崖式下降，这提示答案可以直接当成一个可以从小往大试的量。边界上要注意：
f = 0也是合法答案，即所有楼层都会摔碎鸡蛋这种情况必须能被区分出来；k = 1时没有任何试错余地，只能从第 1 层老老实实往上逐层试；n = 1时只需一次操作。
解法：按移动次数递推可覆盖楼层
核心思路
正向定义「
e枚蛋测n层最少要几次」时，每个状态还要枚举第一次投掷的楼层并处理最坏分支，朴素复杂度达到 $O(kn^2)$。更合适的方向是把答案当作自变量：状态定义：
F(m, e)表示使用e枚鸡蛋、最多投掷m次，能够保证确定临界层的最大连续楼层数。第一次投掷把区间分成三部分：
- 鸡蛋碎了：剩
m - 1次、e - 1枚蛋，下方最多覆盖F(m - 1, e - 1)层；- 鸡蛋没碎：剩
m - 1次、e枚蛋，上方最多覆盖F(m - 1, e)层；- 当前投掷层：1 层。
因而有转移：
\[F(m,e)=F(m-1,e-1)+F(m-1,e)+1\]这不仅是一个可行构造，也是上界。任意策略的第一次投掷都必须同时保证碎与不碎两条分支可解，因此下方不能超过
F(m - 1, e - 1)层，上方不能超过F(m - 1, e)层；反过来，把投掷点放在下方覆盖范围之后，恰好能覆盖两段加当前层。所以转移式给出的就是最大值。边界为
F(0, e) = 0、F(m, 0) = 0。F(m, k)随m单调增加，第一个满足F(m, k) >= n的m就是最少投掷次数。二维状态只依赖上一轮，可压成一维dp[e]；更新时必须从大到小枚举鸡蛋数，避免覆盖仍需使用的上一轮状态。
解题步骤
- 创建
dp[0...k]，初值都为 0；此时表示 0 次投掷能覆盖 0 层。- 每轮把
moves加一，表示允许多投一次。- 从
eggs = k递减到 1，执行dp[eggs] = dp[eggs] + dp[eggs - 1] + 1。- 当
dp[k] >= n时停止，返回moves。
k = 2、n = 6时，覆盖层数如下：
movesdp[1]dp[2]0 0 0 1 1 1 2 2 3 3 3 6 3 次首次覆盖 6 层，所以答案是 3。只有 1 枚蛋时
dp[1]每轮只增加 1，算法自然退化为逐层测试。
代码实现
class Solution {
public int superEggDrop(int k, int n) {
long[] dp = new long[k + 1];
int moves = 0;
while (dp[k] < n) {
moves++;
for (int eggs = k; eggs >= 1; eggs--) {
dp[eggs] = dp[eggs] + dp[eggs - 1] + 1;
}
}
return moves;
}
}
func superEggDrop(k int, n int) int {
dp := make([]int, k+1)
moves := 0
for dp[k] < n {
moves++
for eggs := k; eggs >= 1; eggs-- {
dp[eggs] = dp[eggs] + dp[eggs-1] + 1
}
}
return moves
}
复杂度分析
- 时间复杂度：$O(k \cdot A)$，
A为答案。外层执行A轮，每轮更新k个状态；最坏k = 1时A = n。- 空间复杂度：$O(k)$，使用长度为
k + 1的滚动数组。
关键点总结
- 反转状态：不问「这些楼层要几次」，改问「这些次数最多覆盖几层」。
- 转移中的两项分别对应碎与不碎，两段都必须保证可解，因此相加而不是取最大值。
- 转移既有构造又有上界证明，保证搜索策略完备且最优。
- 一维压缩必须逆序更新，否则会混用本轮和上一轮状态。
- 两个极端可自检：
k = 1时答案是n；当e >= m时，m次投掷恰好覆盖2^m - 1层。
易错点总结
- 正序更新
dp：k = 2时第 2 轮会错误得到dp[2] = 5而不是 3；必须从大到小更新。- 漏掉
+ 1：当前投掷层没有被计入，k = 1时覆盖数甚至不会增长。- 把两条分支取
max：正向求最少次数时取最坏分支；逆向求覆盖层数时，两段互不重叠，必须相加。- 停止条件写成
dp[k] <= n：恰好覆盖n层时还会多算一次，应在dp[k] >= n时停止。- 混淆状态含义：
dp[e]是可保证覆盖的楼层数，不是临界层候选数，也不是已经投掷的楼层编号。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 312. 戳气球 | 困难 | 区间 DP，按「最后戳破哪个」划分区间而非交换状态维度 |
| 486. 预测赢家 | 中等 | 博弈 DP，状态存的是先手净得分差，无需逆向定义 |
| 877. 石子游戏 | 中等 | 博弈 DP，可由奇偶性直接得出必胜结论 |
| 1000. 合并石头的最低成本 | 困难 | 区间 DP 多带一维「剩余堆数」，靠可行性判断剪枝 |
| 1690. 石子游戏 VII | 中等 | 区间博弈 DP 配前缀和，转移只需 $O(1)$ 求区间和 |
| 面试题 08.14. 布尔运算 | 中等 | 区间 DP 按运算符分割，需同时维护真值与假值两种计数 |