原文链接: https://leetcode-cn.com/problems/egg-drop-with-2-eggs-and-n-floors

英文原文

You are given two identical eggs and you have access to a building with n floors labeled from 1 to n.

You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.

In each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.

Return the minimum number of moves that you need to determine with certainty what the value of f is.

 

Example 1:

Input: n = 2
Output: 2
Explanation: We can drop the first egg from floor 1 and the second egg from floor 2.
If the first egg breaks, we know that f = 0.
If the second egg breaks but the first egg didn't, we know that f = 1.
Otherwise, if both eggs survive, we know that f = 2.

Example 2:

Input: n = 100
Output: 14
Explanation: One optimal strategy is:
- Drop the 1st egg at floor 9. If it breaks, we know f is between 0 and 8. Drop the 2nd egg starting from floor 1 and going up one at a time to find f within 8 more drops. Total drops is 1 + 8 = 9.
- If the 1st egg does not break, drop the 1st egg again at floor 22. If it breaks, we know f is between 9 and 21. Drop the 2nd egg starting from floor 10 and going up one at a time to find f within 12 more drops. Total drops is 2 + 12 = 14.
- If the 1st egg does not break again, follow a similar process dropping the 1st egg from floors 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, and 100.
Regardless of the outcome, it takes at most 14 drops to determine f.

 

Constraints:

• 1 <= n <= 1000

中文题目

给你 2 枚相同 的鸡蛋，和一栋从第 1 层到第 n 层共有 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

 

提示：

• 1 <= n <= 1000

通过代码

高赞题解

解法一：动态规划
本题比较直观的解法可以采用动态规划，用 dp[i][j] 表示有 i + 1 枚鸡蛋时，验证 j 层楼需要的最少操作次数， 我们可以分开分析 i = 0 和 i = 1 的情况：

• i = 0 即只剩一枚鸡蛋，此时我们需要从 1 层开始逐层验证才能确保获取确切的 f 值，因此对于任意的 j 都有 dp[0][j] = j
• i = 1，对于任意 j ，第一次操作可以选择在 [1, j] 范围内的任一楼层 k，如果鸡蛋在 k 层丢下后破碎，接下来问题转化成 i = 0 时验证 k - 1 层需要的次数，即 dp[0][k - 1], 总操作次数为 dp[0][k - 1] + 1； 如果鸡蛋在 k 层丢下后没碎，接下来问题转化成 i = 1 时验证 j - k 层需要的次数， 即 dp[1][j - k], 总操作次数为 dp[1][j - k] + 1，考虑最坏的情况，两者取最大值则有 dp[1][j] = min(dp[1][j], max(dp[0][k - 1] + 1, dp[1][j - k] + 1))

class Solution {
public:
    int twoEggDrop(int n) {
        vector<vector<int>> dp(2, vector<int>(n + 1, INT_MAX));
        dp[0][0] = dp[1][0] = 0;
        for (int j = 1; j <= n; ++j) {
            dp[0][j] = j;
        }

        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= j; ++k) {
                dp[1][j] = min(dp[1][j], max(dp[0][k - 1] + 1, dp[1][j - k] + 1));
            }
        }

        return dp[1][n];
    }
};

显然上面的 dp[0][j] 可以优化掉转为一维dp

class Solution {
public:
    int twoEggDrop(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= j; ++k) {
                dp[j] = min(dp[j], max(k, dp[j - k] + 1));
            }
        }
        return dp[n];
    }
};

复杂度分析

• 时间复杂度： O(n²), n为楼层数
• 空间复杂度： O(n)

解法二：数学规律

首先分开看2枚鸡蛋的使用：
第1枚鸡蛋可以视为大范围的覆盖验证，

• 在任意步操作后第1枚鸡蛋仍没有碎，待验证楼层区间为[bottom, n]
• 下一步在任意 i (bottom <= i <= n) 层丢下后，可将验证范围缩小到 [bottom, i - 1] (碎了) 或 [i, n] (没碎)
• 如果一直没碎则可以一直向上覆盖待验证区间，直到 i == n

第2枚鸡蛋视为细粒度逐层验证

• 第1枚鸡蛋破碎后由第2枚鸡蛋检验 [bottom, i - 1] 区间
• 只能按 bottom, bottom + 1 … i - 1 顺序逐层验证才能确保获得 f 确切的值

有了上面的鸡蛋操作规范，我们可以反向推导，假设对于 n 层楼计算并返回要确定 f 确切的值的最小操作次数为 M ， 我们可以有以下结论：

1. 第一次操作必然选择在 x ≤ M 层，这里使用反证法：当 x > M ，如果第一次操作后鸡蛋破碎，则转入第2枚鸡蛋任务，需要 x - 1 次操作逐层验证，总操作次数为 1 + (x - 1) = x > M ，违背总操作次数为 M 的假设
2. 第 k 次操作第1枚鸡蛋的覆盖层数必须小于等于 M - k + 1 ，原因同 1
3. 综合(1, 2)的限制，可以得出 M 次操作可以覆盖的最大楼层数量为 Sum = M + (M - 1) + (M - 2) + … + 1 = (M + 1) * M / 2
4. 得到关系：***(M + 1) * M / 2 ≥ n***，则满足条件的 M 最小值即为最小操作次数，用数学方法求解即可：

   class Solution {
   public:
       int twoEggDrop(int n) {
           return ceil((-1.0 + sqrt(n * 8 + 1)) / 2);
       }
   };

复杂度分析

• 时间复杂度、空间复杂度均为 O(1)

统计信息

通过次数	提交次数	AC比率
2311	3346	69.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言