Hard

题目描述

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从高于 f 的楼层落下的鸡蛋都会破碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破碎。

每次操作，你可以取一枚没有破碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋破碎，你就不能再次使用它。如果某枚鸡蛋扔下后没有破碎，则可以在之后的操作中重复使用这枚鸡蛋。

请你计算并返回要确定 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 <= 10^4

解题思路

这道题有两种主要思路：传统动态规划和逆向思维动态规划。

传统动态规划思路： 定义 dp[i][j] 表示有 i 个鸡蛋，j 层楼时的最少操作次数。对于每一层 x，我们考虑在第 x 层扔鸡蛋：

  • 如果鸡蛋破了，剩下 i-1 个鸡蛋，需要检查 x-1 层
  • 如果鸡蛋没破，还有 i 个鸡蛋，需要检查 j-x 层

状态转移方程：dp[i][j] = 1 + min(max(dp[i-1][x-1], dp[i][j-x])) 对所有 x 取最小值。

逆向思维动态规划（推荐）： 换个角度思考：给定 k 个鸡蛋和 t 次操作，最多能确定多少层楼？定义 dp[t][k] 表示 t 次操作、k 个鸡蛋能确定的最大楼层数。

在第 t 次操作中，如果在某层扔鸡蛋：

  • 鸡蛋破了：能确定下面 dp[t-1][k-1] 层
  • 鸡蛋没破：能确定上面 dp[t-1][k] 层
  • 加上当前这一层

状态转移：dp[t][k] = dp[t-1][k-1] + dp[t-1][k] + 1

最后找到第一个满足 dp[t][k] >= n 的 t 值即为答案。这种方法时间复杂度更优。

代码实现

class Solution {
public:
    int superEggDrop(int k, int n) {
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
        
        int t = 0;
        while (dp[t][k] < n) {
            t++;
            for (int i = 1; i <= k; i++) {
                dp[t][i] = dp[t-1][i-1] + dp[t-1][i] + 1;
            }
        }
        
        return t;
    }
};

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        
        t = 0
        while dp[t][k] < n:
            t += 1
            for i in range(1, k + 1):
                dp[t][i] = dp[t-1][i-1] + dp[t-1][i] + 1
        
        return t

public class Solution {
    public int SuperEggDrop(int k, int n) {
        int[,] dp = new int[n + 1, k + 1];
        
        int t = 0;
        while (dp[t, k] < n) {
            t++;
            for (int i = 1; i <= k; i++) {
                dp[t, i] = dp[t-1, i-1] + dp[t-1, i] + 1;
            }
        }
        
        return t;
    }
}

var superEggDrop = function(k, n) {
    const dp = Array(n + 1).fill().map(() => Array(k + 1).fill(0));
    
    let t = 0;
    while (dp[t][k] < n) {
        t++;
        for (let i = 1; i <= k; i++) {
            dp[t][i] = dp[t-1][i-1] + dp[t-1][i] + 1;
        }
    }
    
    return t;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度传统DP逆向DP
时间复杂度O(kn²)O(k√n)
空间复杂度O(kn)O(k√n)

相关题目