Medium

题目描述

给你两个相同的鸡蛋，以及一个有 n 层楼的建筑，楼层编号从 1 到 n。

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

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

请你计算并返回要确定 f 确切的值的最少操作次数。

示例 1：

输入：n = 2
输出：2
解释：我们可以将第一枚鸡蛋从 1 楼扔下，然后将第二枚鸡蛋从 2 楼扔下。
如果第一枚鸡蛋破碎，那么 f = 0。
如果第二枚鸡蛋破碎但第一枚没有破碎，那么 f = 1。
如果两枚鸡蛋都没有破碎，那么 f = 2。

示例 2：

输入：n = 100
输出：14
解释：一种最优的策略是：
- 在第 9 层扔下第 1 枚鸡蛋。如果破碎，我们知道 f 在 0 到 8 之间。从第 1 层开始用第 2 枚鸡蛋一层一层往上扔，最多需要扔 8 次就能找到 f。总扔鸡蛋次数为 1 + 8 = 9。
- 如果第 1 枚鸡蛋没有破碎，在第 22 层扔下第 1 枚鸡蛋。如果破碎，我们知道 f 在 9 到 21 之间。从第 10 层开始用第 2 枚鸡蛋一层一层往上扔，最多需要扔 12 次就能找到 f。总扔鸡蛋次数为 2 + 12 = 14。
- 如果第 1 枚鸡蛋仍然没有破碎，按照类似的方法在第 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100 层扔下第 1 枚鸡蛋。
无论结果如何，最多需要扔 14 次鸡蛋就能确定 f。

约束条件：

  • 1 <= n <= 1000

解题思路

这是一个经典的动态规划问题。关键在于理解状态转移：

基本思路： 我们定义 dp[i] 为确定 i 层楼的关键楼层最少需要的操作次数。

当我们在第 j 层扔第一个鸡蛋时，有两种情况：

  1. 鸡蛋破碎：说明关键楼层在 [1, j-1] 范围内，我们需要用剩下的一个鸡蛋逐层测试，最多需要 j-1 次
  2. 鸡蛋不破碎：说明关键楼层在 [j, n] 范围内，问题转化为在剩余的 n-j 层中寻找，需要 dp[n-j] 次

因此状态转移方程为：dp[i] = min(max(j-1, dp[i-j]) + 1) for all valid j

优化思路： 可以通过数学分析发现，最优策略是让两种情况的次数尽可能接近。设第一次在第 x 层扔，最坏情况需要 max(x-1, dp[n-x]) + 1 次。我们要找到使这个值最小的 x。

还有一种更巧妙的思路：反向思考，如果我们有 m 次操作机会，最多能测试多少层楼？这样可以用更简洁的代码实现。

代码实现

class Solution {
public:
    int twoEggDrop(int n) {
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++) {
            dp[i] = i;  // 最坏情况：逐层测试
            for (int j = 1; j < i; j++) {
                dp[i] = min(dp[i], max(j, dp[i - j]) + 1);
            }
        }
        return dp[n];
    }
};

class Solution:
    def twoEggDrop(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = i  # 最坏情况：逐层测试
            for j in range(1, i):
                dp[i] = min(dp[i], max(j, dp[i - j]) + 1)
        return dp[n]

public class Solution {
    public int TwoEggDrop(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = i;  // 最坏情况：逐层测试
            for (int j = 1; j < i; j++) {
                dp[i] = Math.Min(dp[i], Math.Max(j, dp[i - j]) + 1);
            }
        }
        return dp[n];
    }
}

var twoEggDrop = function(n) {
    const dp = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        dp[i] = i;  // 最坏情况：逐层测试
        for (let j = 1; j < i; j++) {
            dp[i] = Math.min(dp[i], Math.max(j, dp[i - j]) + 1);
        }
    }
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n²)
空间复杂度O(n)

相关题目