LeetCode 887. 鸡蛋掉落
题目描述
题意分析
有
k枚相同的鸡蛋和n层楼。存在一个未知临界值f，从不高于f的楼层扔下鸡蛋不会碎，从高于f的楼层扔下就会碎；f可以为0，也可以为n。每次可以选择楼层测试，不碎的鸡蛋可以继续使用，碎掉的鸡蛋不能再用。要求设计一种策略，使无论实际
f是多少，都能确定它的准确值，并让最坏情况下的投掷次数尽可能少。返回的是这个保证次数，不是某一次幸运找到答案所花的次数。
解法：按移动次数递推可覆盖楼层
核心思路
[!blue]
直接计算“这些楼层最少要几次”，需要考虑每次从哪里扔，以及碎和不碎两种结果。换一个方向：给定鸡蛋数与投掷次数预算，最多能保证解决多少层楼，再找到覆盖
n层的最小预算。设
F(moves, eggs)表示用eggs枚鸡蛋、至多投掷moves次，能够保证确定临界值的最大楼层数。没有投掷次数或没有鸡蛋时，都无法判断任何未知楼层，因此对应覆盖数为零。现在先投掷一次。如果鸡蛋碎了，临界值在测试楼层下方，剩余
moves - 1次和eggs - 1枚蛋，最多处理下方F(moves - 1, eggs - 1)层。如果没碎，临界值在当前楼层或更高，所有鸡蛋仍可使用，最多再处理上方F(moves - 1, eggs)层。加上本次测试楼层，得到递推：F(moves, eggs) = F(moves - 1, eggs - 1) + 1 + F(moves - 1, eggs)。这个和既能达到，也是上界。把首次测试楼层选在下方恰好留出碎蛋分支覆盖数的位置，两种结果都能在剩余预算内解决，因此可以覆盖两段加当前层。反过来，任何首次测试都要同时保证两种结果可解，下方和上方的未知楼层数分别不能超过各自分支的能力，所以总数也不可能更大。
一维数组
dp[eggs]保存上一轮预算的覆盖数。每增加一次投掷预算，按鸡蛋数从大到小更新dp[eggs] = dp[eggs] + dp[eggs - 1] + 1。倒序使两个来源都还是上一轮的值，避免把本轮新增加的投掷能力重复使用。覆盖数随预算增加而增大，第一次出现
dp[k] >= n时，当前预算可以保证成功，而更少的预算无法覆盖全部楼层，因此就是最优答案。dp统计的是楼层数；临界值虽然有从0到n共n + 1种可能，停止目标仍应是n。
解题步骤
- 创建
dp[0..k]并全部初始化为零，令moves = 0。- 当
dp[k] < n时，将moves加一，允许多一次投掷。- 从
eggs = k递减到1，更新dp[eggs] = dp[eggs] + dp[eggs - 1] + 1，保留dp[0] = 0。- 首次达到
dp[k] >= n后结束，返回moves。只有一枚蛋时每轮覆盖数增加一，自然得到逐层测试所需的n次。
代码实现
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(kA)$，其中
A是最终最少投掷次数。每增加一次预算就更新k个状态；一枚蛋时A = n，并不总是对数次数。- 空间复杂度：$O(k)$，只保存当前一轮的覆盖数，转移时通过倒序保留所需的旧状态。
关键点总结
[!green]
- 从求最少次数转为求给定次数能覆盖的最大楼层数，避免逐个枚举首次投掷位置。
- 碎和不碎对应测试楼层上下两段，两段都必须能处理，所以覆盖数相加，并计入测试层本身。
- 递推同时有可行策略和覆盖上界，首次达到目标的预算才具有最优性保证。
- 一维状态的倒序更新保证两条分支都只使用少一次投掷的能力。
易错点总结
[!yellow]
- 鸡蛋数正序更新，会读取本轮刚增加的
dp[eggs - 1]，把额外投掷能力混入同一轮，夸大覆盖数。- 漏掉
+ 1，就没有计入当前测试楼层，初始全零状态甚至无法增长。- 对两分支取最大值，会忽略首次测试把楼层分成上下两段的含义；此处求覆盖数，应把两段相加。
- 循环条件使用
dp[k] <= n，会在刚好覆盖目标时多算一轮，应在大于等于目标时结束。- 将目标写成
n + 1，混淆了楼层数和临界值候选数量，会导致额外投掷。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1884. 鸡蛋掉落-两枚鸡蛋 | 中等 | 原题固定两枚鸡蛋，是本题资源数固定后的特例，可采用更专门的递推或分段策略。 |
| 458. 可怜的小猪 | 困难 | 同样从实验次数能区分多少情况出发，本题鸡蛋破碎会改变剩余资源，状态容量递推不同。 |