高楼扔鸡蛋

## 1 题目

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

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

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

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

**示例 1：**

```txt
输入：k = 1, n = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。
如果它没碎，那么肯定能得出 f = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。
```

**示例 2：**

```txt
输入：k = 2, n = 6
输出：3
```

**示例 3：**

```txt
输入：k = 3, n = 14
输出：4
```

**提示：**

* 1 <= k <= 100
* 1 <= n <= 104

## 2 解题思路

### 2.1 动态规划

#### 2.1.1 问题分析

我们可以考虑使用动态规划来做这道题，状态可以表示成 $(k,n)$，其中 $k$ 为鸡蛋数，$n$ 为楼层数。当我们从第 $x$ 楼扔鸡蛋的时候：

* 如果鸡蛋不碎，那么状态变成 $(k,n-x)$，即我们鸡蛋的数目不变，但答案只可能在上方的 $n-x$ 层楼了。也就是说，我们把原问题缩小成了一个规模为 $(k,n-x)$ 的子问题；
* 如果鸡蛋碎了，那么状态变成 $(k-1,x-1)$，即我们少了一个鸡蛋，但我们直到答案只可能在 $x$ 楼下方的 $x-1$ 层楼中了。也就是说，我们把原问题缩小成了一个规模为 $(k-1,x-1)$ 的子问题。

![](/media/202104/2021-04-07_214952.png)

这样一来，我们定义 $dp(k,n)$ 为在状态 $(k,n)$ 下最少需要的步数。根据以上分析，我们可以列出状态转移方程：

$$
dp(k,n)=1+\min_{1 \leq x \leq n}(max(dp(k-1,x-1),dp(k,n-x)))
$$

这个状态转移方程是如何得来的呢？对于 $dp(k,n)$ 而言，我们像上面分析的那样，枚举第一个鸡蛋扔在的楼层数 $x$。由于我们并不知道真正的 $f$ 值，因此我们必须保证**鸡蛋碎了之后接下来需要的步数**和**鸡蛋没碎之后需要的步数**二者**最大值**最小，这样就保证了在**最坏情况下（也就是无论 $f$ 的值如何）**$dp(k,n)$ 的值最小。

#### 2.1.2 解题方法

动态规划的解法有**递归**、**备忘录优化**、**DP Table 优化**。

##### 2.1.2.1 递归方法

```java
/**
 * 最坏情况下扔鸡蛋的次数（版本 1：递归）
 *
 * @param k 鸡蛋个数
 * @param n 总楼层数
 * @return 最坏情况下扔鸡蛋的次数
 */
public int dpV1(int k, int n) {
    //  如果只有 1 个鸡蛋，则所有楼层都需要试一下
    if (k == 1) {
        return n;
    }
    //  如果楼层数为 0，则不需要进行尝试，直接返回 0 即可
    if (n == 0) {
        return 0;
    }

int res = n;
    for (int i = 1; i <= n; i++) {
        res = Math.min(
                res,
                Math.max(
                        //  鸡蛋碎了
                        dpV1(k - 1, i - 1),
                        //  鸡蛋没碎
                        dpV1(k, n - i)
                ) + 1
        );
    }
    return res;
}

/**
 * 887. 鸡蛋掉落（版本 1：递归）
 * 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
 * 已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
 * 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
 * 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
 *
 * @param k 目标楼层
 * @param n 总楼层
 * @return 要确定 f 确切的值 的 最小操作次数
 */
public int superEggDropV1(int k, int n) {
    return dpV1(k, n);
}
```

##### 2.1.2.2 备忘录优化

```java
/**
 * 最坏情况下扔鸡蛋的次数（版本 2：备忘录优化）
 *
 * @param k 鸡蛋个数
 * @param n 总楼层数
 * @return 最坏情况下扔鸡蛋的次数
 */
public int dpV2(int k, int n, int[][] memo) {
    //  如果只有 1 个鸡蛋，则所有楼层都需要试一下
    if (k == 1) {
        return n;
    }
    //  如果楼层数为 0，则不需要进行尝试，直接返回 0 即可
    if (n == 0) {
        return 0;
    }

//  如果数据在备忘录中已经存在的话，直接返回即可
    if (memo[k][n] != Integer.MAX_VALUE) {
        return memo[k][n];
    }

for (int i = 1; i <= n; i++) {
        memo[k][n] = Math.min(
                memo[k][n],
                Math.max(
                        //  鸡蛋碎了
                        dpV2(k - 1, i - 1, memo),
                        //  鸡蛋没碎
                        dpV2(k, n - i, memo)
                ) + 1
        );
    }
    return memo[k][n];
}

/**
 * 887. 鸡蛋掉落（版本 2：备忘录优化）
 * 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
 * 已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
 * 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
 * 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
 *
 * @param k 目标楼层
 * @param n 总楼层
 * @return 要确定 f 确切的值 的 最小操作次数
 */
public int superEggDropV2(int k, int n) {
    //  备忘录
    int[][] memo = new int[k + 1][n + 1];
    for (int i = 0; i < memo.length; i++) {
        Arrays.fill(memo[i], Integer.MAX_VALUE);
    }
    return dpV2(k, n, memo);
}
```

##### 2.1.2.3 二分查找优化

如果我们直接暴力求解每个状态的 $dp$ 值，时间复杂度为 $O(kn^2)$，即一共有 $O(kn)$ 个状态，对于每个状态枚举扔鸡蛋的楼层 $x$，需要 $O(n)$ 的时间。这无疑在当前数据范围下是会超出时间限制的，因此我们需要想办法优化枚举的时间复杂度。

随我们观察到 $dp(k,n)$ 是一个关于 $n$ 的单调递增函数，也就是说在鸡蛋数 $k$ 固定的情况下，楼层数 $n$ 越多，需要的步数一定不会变少。在**2.1.1 问题分析**中的状态转移方程中，第一项 $T_1(x)=dp(k-1,x-1)$ 是一个随 $x$ 的增加而单调递增的函数，第二项 $T_2(x)=dp(k,n-x)$ 是一个随着 $x$ 的增加而单调递减的函数。

![887_fig1.jpg (2560×1213)](/media/202104/2021-04-08_141222.png)

如上图所示，如果这两个函数都是连续函数，那么我们只需要找出这两个函数的交点，在交点处就能保证这两个函数的最大值最小。但在本题中，$T_1(x)$ 和 $T_2(x)$ 都是离散函数，也就是说 $x$ 的值只能取 1、2、3 等等。在这种情况下，我们需要找到最大的满足 $T_1(x) \lt T_2(x)$ 中的 $x_0$，以及最小的满足 $T_1(x) \ge T_2(x)$ 的 $x_1$，对应到上图中，就是离这两个函数（想象中的）交点左右两侧最近的整数。

我们只需要比较在 $x_0$ 和 $x_1$ 处两个函数的最大值，取一个最小的作为 $x$ 即可。

参考代码如下：

```java
/**
 * 最坏情况下扔鸡蛋的次数（版本 3：二分查找优化）
 *
 * @param k 鸡蛋个数
 * @param n 总楼层数
 * @return 最坏情况下扔鸡蛋的次数
 */
public int dpV3(int k, int n, int[][] memo) {
    //  如果只有 1 个鸡蛋，则所有楼层都需要试一下
    if (k == 1) {
        return n;
    }
    //  如果楼层数为 0，则不需要进行尝试，直接返回 0 即可
    if (n == 0) {
        return 0;
    }

//  如果数据在备忘录中已经存在的话，直接返回即可
    if (memo[k][n] != Integer.MAX_VALUE) {
        return memo[k][n];
    }

int left = 1, right = n + 1, res = Integer.MAX_VALUE;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        //  鸡蛋碎了
        int broken = dpV3(k - 1, mid - 1, memo);
        //  鸡蛋没碎
        int notBroken = dpV3(k, n - mid, memo);
        if (broken > notBroken) {
            right = mid - 1;
            res = Math.min(res, broken + 1);
        } else if (broken < notBroken) {
            left = mid + 1;
            res = Math.min(res, notBroken + 1);
        } else if (broken == notBroken) {
            right = mid - 1;
            res = Math.min(res, broken + 1);
        }
    }
    memo[k][n] = res;
    return res;
}
```

## 3 参考文献

1. [887. 鸡蛋掉落](https://leetcode-cn.com/problems/super-egg-drop)。
2. [《鸡蛋掉落》官方题解](https://leetcode-cn.com/problems/super-egg-drop/solution/ji-dan-diao-luo-by-leetcode-solution-2)。