LeetCode 887. 鸡蛋掉落

Categories:

题目描述
思路分析
1. 解法一：逆向 DP + 二分查找（推荐）
2. 解法二：经典 DP + 二分优化
相似题目

题目描述

✅ 887. 鸡蛋掉落

思路分析

解法一：逆向 DP + 二分查找（推荐）

核心思路：

原始 DP 定义 dp[i][j] 为 i 层楼 j 个鸡蛋时的最少操作次数，状态转移需要枚举每层楼，时间复杂度为 O(kn²)，无法通过。

换一个角度：定义 dp[m][k] 为使用 m 次操作、k 个鸡蛋，最多能确认多少层楼。

对于第 m 次操作，选择某层楼扔鸡蛋：

鸡蛋碎了：还剩 m-1 次操作、k-1 个鸡蛋，向下最多能检查 dp[m-1][k-1] 层。

鸡蛋没碎：还剩 m-1 次操作、k 个鸡蛋，向上最多能检查 dp[m-1][k] 层。

加上当前这一层，得状态转移：dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1。

从 m = 1 开始递增，直到 dp[m][k] >= n，此时的 m 即为答案。

由于答案 m 最大为 O(log n)（二分时），外层循环次数很少，总时间复杂度为 O(k log n)。

复杂度分析：

时间复杂度：O(k log n)，其中 k 为鸡蛋数，n 为楼层数，操作次数 m 上界为 O(log n)。

空间复杂度：O(k)，只需保存上一行 DP 值。

class Solution {
    public int superEggDrop(int k, int n) {
        // dp[j] 表示当前操作次数下，j 个鸡蛋最多能检查的楼层数
        int[] dp = new int[k + 1];
        int m = 0;

        // 不断增加操作次数，直到能覆盖 n 层楼
        while (dp[k] < n) {
            m++;
            // 从右往左更新，避免本轮数据污染
            for (int j = k; j >= 1; j--) {
                // 鸡蛋碎了检查下方 + 鸡蛋未碎检查上方 + 当前楼层
                dp[j] = dp[j - 1] + dp[j] + 1;
            }
        }

        return m;
    }
}

func superEggDrop(k int, n int) int {
    // dp[j] 表示当前操作次数下，j 个鸡蛋最多能检查的楼层数
    dp := make([]int, k+1)
    m := 0

    // 不断增加操作次数，直到能覆盖 n 层楼
    for dp[k] < n {
        m++
        // 从右往左更新，避免本轮数据污染
        for j := k; j >= 1; j-- {
            // 鸡蛋碎了检查下方 + 鸡蛋未碎检查上方 + 当前楼层
            dp[j] = dp[j-1] + dp[j] + 1
        }
    }

    return m
}

解法二：经典 DP + 二分优化

核心思路：

定义 dp[i][j] 为 i 层楼、j 个鸡蛋时的最少操作次数。

在第 x 层扔鸡蛋：碎了则答案在 [1, x-1]，未碎则答案在 [x+1, i]，取两者最大值再加 1。

状态转移：dp[i][j] = min over x of (max(dp[x-1][j-1], dp[i-x][j]) + 1)。

关键优化：dp[x-1][j-1] 随 x 单调递增，dp[i-x][j] 随 x 单调递减，两者交叉点即最优解，用二分查找定位，单次转移从 O(n) 降到 O(log n)。

整体时间复杂度为 O(kn log n)。

复杂度分析：

时间复杂度：O(kn log n)，其中 k 为鸡蛋数，n 为楼层数，二分查找最优扔鸡蛋楼层。

空间复杂度：O(kn)，二维 DP 表。

class Solution {
    public int superEggDrop(int k, int n) {
        // dp[i][j] 表示 i 层楼、j 个鸡蛋时的最少操作次数
        int[][] dp = new int[n + 1][k + 1];

        // 初始化：0 层楼需 0 次，1 层楼需 1 次
        for (int j = 1; j <= k; j++) {
            dp[1][j] = 1;
        }
        // 初始化：只有 1 个鸡蛋时，需要逐层检查
        for (int i = 1; i <= n; i++) {
            dp[i][1] = i;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= k; j++) {
                // 二分查找最优扔鸡蛋楼层 x
                int lo = 1, hi = i;
                while (lo + 1 < hi) {
                    int mid = lo + (hi - lo) / 2;
                    int breakCase = dp[mid - 1][j - 1];
                    int noBreakCase = dp[i - mid][j];
                    if (breakCase < noBreakCase) {
                        lo = mid;
                    } else if (breakCase > noBreakCase) {
                        hi = mid;
                    } else {
                        lo = hi = mid;
                    }
                }
                // 取 lo 和 hi 两个候选点的较小值
                dp[i][j] = 1 + Math.min(
                    Math.max(dp[lo - 1][j - 1], dp[i - lo][j]),
                    Math.max(dp[hi - 1][j - 1], dp[i - hi][j])
                );
            }
        }

        return dp[n][k];
    }
}

func superEggDrop(k int, n int) int {
    // dp[i][j] 表示 i 层楼、j 个鸡蛋时的最少操作次数
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, k+1)
    }

    // 初始化：1 层楼需 1 次操作
    for j := 1; j <= k; j++ {
        dp[1][j] = 1
    }
    // 初始化：只有 1 个鸡蛋时，需要逐层检查
    for i := 1; i <= n; i++ {
        dp[i][1] = i
    }

    for i := 2; i <= n; i++ {
        for j := 2; j <= k; j++ {
            // 二分查找最优扔鸡蛋楼层 x
            lo, hi := 1, i
            for lo+1 < hi {
                mid := lo + (hi-lo)/2
                breakCase := dp[mid-1][j-1]
                noBreakCase := dp[i-mid][j]
                if breakCase < noBreakCase {
                    lo = mid
                } else if breakCase > noBreakCase {
                    hi = mid
                } else {
                    lo, hi = mid, mid
                }
            }
            // 取 lo 和 hi 两个候选点的较小值
            dp[i][j] = 1 + min(
                max(dp[lo-1][j-1], dp[i-lo][j]),
                max(dp[hi-1][j-1], dp[i-hi][j]),
            )
        }
    }

    return dp[n][k]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

相似题目

题目	难度	考察点
1884. 鸡蛋掉落-两枚鸡蛋	中等	数学、动态规划
410. 分割数组的最大值	困难	二分查找、动态规划
1011. 在 D 天内送达包裹的能力	中等	二分查找
875. 爱吃香蕉的珂珂	中等	二分查找
312. 戳气球	困难	区间动态规划
486. 预测赢家	中等	博弈、动态规划
1278. 分割回文串 III	困难	动态规划、二分

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/65474304