1884-鸡蛋掉落-两枚鸡蛋

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 11:09:49 2023-09-13 11:09:49 Updated    

给你 **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
**解释：** 一种最优的策略是：
- 将第一枚鸡蛋从 9 楼扔下。如果碎了，那么 f 在 0 和 8 之间。将第二枚从 1 楼扔下，然后每扔一次上一层楼，在 8 次内找到 f 。总操作次数 = 1 + 8 = 9 。
- 如果第一枚鸡蛋没有碎，那么再把第一枚鸡蛋从 22 层扔下。如果碎了，那么 f 在 9 和 21 之间。将第二枚鸡蛋从 10 楼扔下，然后每扔一次上一层楼，在 12 次内找到 f 。总操作次数 = 2 + 12 = 14 。
- 如果第一枚鸡蛋没有再次碎掉，则按照类似的方法从 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99 和 100 楼分别扔下第一枚鸡蛋。
不管结果如何，最多需要扔 14 次来确定 f 。

提示：

  • 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))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

1
2
3
4
5
6
7
8
9
10
11
12
13
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 最小值即为最小操作次数，用数学方法求解即可：
    1
    2
    3
    4
    5
    6
    class Solution {
    public:
        int twoEggDrop(int n) {
            return ceil((-1.0 + sqrt(n * 8 + 1)) / 2);
        }
    };
    复杂度分析
  • 时间复杂度、空间复杂度均为 O(1)
 Comments
On this page
1884-鸡蛋掉落-两枚鸡蛋