887. 鸡蛋掉落

LeetCode：887. 鸡蛋掉落
难度：困难
归类：动态规划、数学、二分查找
主解法：按操作次数反推可确定的楼层数

先给结论

直接定义“k 枚鸡蛋、n 层楼最少扔几次”时，需要枚举第一次扔鸡蛋的楼层，转移不够轻量。换一个角度：

dp[m][k] 表示最多操作 m 次、拥有 k 枚鸡蛋时，在最坏情况下最多能确定多少层楼。

第一次扔下鸡蛋只有两种结果：

碎了： 还剩 m - 1 次操作和 k - 1 枚鸡蛋，可以确定下方 dp[m - 1][k - 1] 层。
没碎： 还剩 m - 1 次操作和 k 枚鸡蛋，可以确定上方 dp[m - 1][k] 层。
再加上本次测试的这一层。

所以：

dp[m][k] = dp[m - 1][k - 1] + 1 + dp[m - 1][k]

从 m = 1 开始增加操作次数，第一个满足 dp[m][k] >= n 的 m 就是答案。

题目描述

有一栋共 n 层的楼和 k 枚相同的鸡蛋。存在一个临界楼层 f，满足 0 <= f <= n：

从高于 f 的楼层扔鸡蛋，鸡蛋一定会碎。
从 f 或低于 f 的楼层扔鸡蛋，鸡蛋一定不会碎。

鸡蛋碎后不能继续使用，没有碎则可以重复使用。求无论真实的 f 是多少，确定其准确值所需的最少操作次数。

示例：

输入：k = 2, n = 6
输出：3

另一个示例：

输入：k = 3, n = 14
输出：4

题目约束：

1 <= k <= 100。
1 <= n <= 10^4。

这里求的是最坏情况下的最少操作次数，不能只让平均次数较小，也不能假设鸡蛋一定碎或一定不碎。

1.`dp` 数组含义

先定义标准二维状态：

dp[m][k] 表示最多操作 m 次、拥有 k 枚鸡蛋时，
无论临界楼层在哪里，最多能确定的连续楼层数。

这里的值不是“最少操作次数”，而是给定操作预算后能够覆盖的楼层规模。

只要找到最小的 m，使得：

dp[m][k] >= n

就说明 m 次操作足以覆盖整栋楼，并且比 m 更小的操作次数都不够，因此这个 m 就是题目答案。

2. 确定状态转移方程

假设还可以操作 m 次，并有 k 枚鸡蛋。

第一次测试的位置应当这样安排：

下方预留 dp[m - 1][k - 1] 层
当前测试 1 层
上方预留 dp[m - 1][k] 层

如果鸡蛋碎了，临界楼层只能在当前层下方。此时损失一枚鸡蛋和一次操作，最多还能处理：

dp[m - 1][k - 1]

如果鸡蛋没碎，临界楼层在当前层或更高处。此时只消耗一次操作，最多还能处理：

dp[m - 1][k]

两个分支都必须能够完成判断，所以总覆盖楼层数为：

dp[m][k]
= dp[m - 1][k - 1] + 1 + dp[m - 1][k]

这个公式既是上界，也是可以实际构造出的策略：

任何策略第一次测试后都只能分成“碎”和“没碎”两个分支，因此不可能覆盖更多楼层。
把第一次测试放在下方可覆盖区间之后的一层，两个分支恰好都能由上一轮状态处理，因此公式中的楼层数确实可以覆盖。

3.`dp` 数组如何初始化

基础状态为：

dp[0][k] = 0
dp[m][0] = 0

含义分别是：

没有操作次数时，无论有多少鸡蛋，都无法测试任何楼层。
没有鸡蛋时，无论还有多少次操作，也无法测试任何楼层。

由递推式还可以得到：

dp[m][1] = m

只有一枚鸡蛋时，为避免过早碎掉，只能从低到高逐层测试；m 次最多确定 m 层。这与题目的直觉一致。

虽然题目保证 n >= 1，实现对 n = 0 也会自然返回 0。

4. 确定遍历顺序

二维状态 dp[m][k] 只依赖上一行：

dp[m - 1][k - 1]
dp[m - 1][k]

所以二维写法应当：

从小到大枚举操作次数 m。
在当前行中枚举鸡蛋数 k。
每算完一行，就检查 dp[m][k] 是否已经覆盖 n 层。

空间压缩为一维数组后：

dp[k] = dp[k] + dp[k - 1] + 1

此时等号右边的 dp[k] 和 dp[k - 1] 都必须来自“上一轮操作次数”，所以鸡蛋数必须倒序遍历。

如果正序遍历，dp[k - 1] 已经是本轮更新后的值，相当于在同一次操作中重复使用新的状态，会高估能够覆盖的楼层数。

5. 举例打印`dp` 数组

以 k = 2、n = 6 为例。

dp[m][k] 的行表示最多操作次数，列表示鸡蛋数量：

`m \ k`	`0` 枚	`1` 枚	`2` 枚
`0` 次	`0`	`0`	`0`
`1` 次	`0`	`1`	`1`
`2` 次	`0`	`2`	`3`
`3` 次	`0`	`3`	`6`

其中：

dp[3][2]
= dp[2][1] + 1 + dp[2][2]
= 2 + 1 + 3
= 6

两次操作最多覆盖 3 层，不足以判断 6 层；三次操作恰好覆盖 6 层，所以答案是 3。

一维数组的变化为：

初始：    [0, 0, 0]
1 次后： [0, 1, 1]
2 次后： [0, 2, 3]
3 次后： [0, 3, 6]

代码实现

原文的 JavaScript 参考实现来自 JoshCrozier/leetcode-javascript，使用“鸡蛋数 + 楼层数”的记忆化 DP 和二分优化。该实现思路可行，但原正文没有给出真实状态、转移方程或二分成立的依据。本文改用与上述五步推导直接对应的“操作次数 + 鸡蛋数”动态规划。

标准二维 DP

/**
 * @param {number} k
 * @param {number} n
 * @return {number}
 */
var superEggDrop2D = function (k, n) {
    // dp[moves][eggs]：最多操作 moves 次、拥有 eggs 枚鸡蛋时，
    // 在最坏情况下最多能够确定的楼层数
    const dp = Array.from({ length: n + 1 }, () =>
        new Array(k + 1).fill(0)
    );

    // 枚举允许的操作次数；只有一枚鸡蛋时最多需要操作 n 次
    for (let moves = 1; moves <= n; moves++) {
        // 计算当前操作次数下，不同鸡蛋数量能够覆盖的楼层数
        for (let eggs = 1; eggs <= k; eggs++) {
            // 碎了：还剩 moves - 1 次操作和 eggs - 1 枚鸡蛋
            const broken = dp[moves - 1][eggs - 1];

            // 没碎：还剩 moves - 1 次操作，鸡蛋数量不变
            const notBroken = dp[moves - 1][eggs];

            // 下方可覆盖楼层 + 当前测试楼层 + 上方可覆盖楼层
            dp[moves][eggs] =
                broken + 1 + notBroken;
        }

        // k 枚鸡蛋已经能够覆盖 n 层，当前 moves 就是最少操作次数
        if (dp[moves][k] >= n) {
            return moves;
        }
    }

    // 题目保证 n >= 1；保留该返回值以兼容 n = 0
    return 0;
};

dp 使用 Array.from 一次初始化为 n + 1 行、k + 1 列，并全部填充为 0。moves 表示当前允许的操作次数，从 1 枚举到 n。每计算完一行，就判断 k 枚鸡蛋是否已经能够覆盖 n 层；如果可以，立即返回当前的 moves。只有一枚鸡蛋时，逐层测试也一定能在 n 次内得到答案，因此循环上界设为 n 即可。n = 0 时不会进入循环，直接返回 0。

一维空间优化

/**
 * @param {number} k
 * @param {number} n
 * @return {number}
 */
var superEggDrop = function (k, n) {
    // dp[eggs]：当前操作次数下，eggs 枚鸡蛋最多能确定的楼层数
    const dp = new Array(k + 1).fill(0);
    let moves = 0;

    // 只要 k 枚鸡蛋还不能覆盖 n 层，就增加一次操作机会
    while (dp[k] < n) {
        moves++;

        // 必须倒序更新，保证 dp[eggs - 1] 仍是上一轮的状态
        for (let eggs = k; eggs >= 1; eggs--) {
            // 旧 dp[eggs]：鸡蛋没碎时可以覆盖的上方楼层
            // dp[eggs - 1]：鸡蛋碎掉时可以覆盖的下方楼层
            // 1：本次测试的楼层
            dp[eggs] = dp[eggs] + dp[eggs - 1] + 1;
        }
    }

    // 第一个使 dp[k] >= n 的操作次数就是答案
    return moves;
};

边界与陷阱

只有一枚鸡蛋： 必须逐层测试，答案为 n。
只有一层楼： 一次操作即可确定 f 是 0 还是 1。
f 可以等于 0： 第一层就碎时，仍要能确定临界楼层为 0。
f 可以等于 n： 所有测试都不碎也是合法情况。
不能直接每次扔中间层： 鸡蛋数量有限时，碎与不碎后的资源并不对称。
不能只考虑最好或平均情况： 两个分支要取最坏情况，并保证都能完成判断。
一维 DP 必须倒序： 正序会读取本轮刚更新的 dp[eggs - 1]。
停止条件是 >= n： 能覆盖的楼层数不必恰好等于 n。
dp 表示楼层数： 不要把 n + 1 个可能的 f 值误当成要覆盖 n + 1 层。

复杂度分析

设最终答案为 M。

标准二维 DP：

时间复杂度：O(kM)。
空间复杂度：O(kn)，因为代码预先创建了完整的二维数组。

一维空间优化：

时间复杂度：O(kM)。
空间复杂度：O(k)。

由于一枚鸡蛋时最多操作 n 次，所以 M <= n。因此时间复杂度也可以写成上界 O(kn)，但 O(kM) 更准确。

当鸡蛋足够多时，覆盖楼层数增长很快。事实上：

dp[m][k] = C(m, 1) + C(m, 2) + ... + C(m, min(m, k))

这也解释了为什么实际循环轮数通常远小于 n。

ON THIS PAGE

#887. 鸡蛋掉落

#先给结论

#题目描述

#1.dp 数组含义

#2. 确定状态转移方程

#3.dp 数组如何初始化

#4. 确定遍历顺序

#5. 举例打印dp 数组

#代码实现

#标准二维 DP

#一维空间优化

#边界与陷阱

#复杂度分析