0887. 鸡蛋掉落

• 标签：数学、二分查找、动态规划
• 难度：困难

题目链接

• 0887. 鸡蛋掉落 - 力扣

题目大意

描述：给定一个整数 k 和整数 n，分别代表 k 枚鸡蛋和可以使用的一栋从第 1 层到第 n 层楼的建筑。

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

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

要求：计算并返回要确定 f 确切值的最小操作次数是多少。

说明：

• $1 \le k \le 100$。
• $1 \le n \le 10^4$。

示例：

• 示例 1：

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

解题思路

这道题目的题意不是很容易理解，我们先把题目简化一下，忽略一些限制条件，理解简单情况下的题意。然后再一步步增加限制条件，从而弄明白这道题目的意思，以及思考清楚这道题的解题思路。

我们先忽略 k 个鸡蛋这个条件，假设有无限个鸡蛋。

现在有 1 ~ n 一共 n 层楼。已知存在楼层 f，低于等于 f 层的楼层扔下去的鸡蛋都不会碎，高于 f 的楼层扔下去的鸡蛋都会碎。

当然这个楼层 f 的确切值题目没有给出，需要我们一次次去测试鸡蛋最高会在哪一层不会摔碎。

在每次操作中，我们可以选定一个楼层，将鸡蛋扔下去：

• 如果鸡蛋没摔碎，则可以继续选择其他楼层进行测试。
• 如果鸡蛋摔碎了，则该鸡蛋无法继续测试。

现在题目要求：已知有 n 层楼，无限个鸡蛋，求出至少需要扔几次鸡蛋，才能保证无论 f 是多少层，都能将 f 找出来？

最简单且直观的想法：

1. 从第 1 楼开始扔鸡蛋。1 楼不碎，再去 2 楼扔。
2. 2 楼还不碎，就去 3 楼扔。
3. ……
4. 直到鸡蛋碎了，也就找到了鸡蛋不会摔碎的最高层 f。

用这种方法，最坏情况下，鸡蛋在第 n 层也没摔碎。这种情况下我们总共试了 n 次才确定鸡蛋不会摔碎的最高楼层 f。

下面再来说一下比 n 次要少的情况。

如果我们可以通过二分查找的方法，先从 1 ~ n 层的中间层开始扔鸡蛋。

• 如果鸡蛋碎了，则从第 1 层到中间层这个区间中去扔鸡蛋。
• 如果鸡蛋没碎，则从中间层到第 n 层这个区间中去扔鸡蛋。

每次扔鸡蛋都从区间的中间层去扔，这样每次都能排除当前区间一半的答案，从而最终确定鸡蛋不会摔碎的最高楼层 f。

通过这种二分查找的方法，可以优化到 $\log n$ 次就能确定鸡蛋不会摔碎的最高楼层 f。

因为 $\log n \le n$，所以通过二分查找的方式，「至少」比线性查找的次数要少。

同样，我们还可以通过三分查找、五分查找等等方式减少次数。

这是在不限制鸡蛋个数的情况下，现在我们来限制一下鸡蛋个数为 k。

现在题目要求：已知有 n 层楼，k 个鸡蛋，求出至少需要扔几次鸡蛋，才能保证无论 f 是多少层，都能将 f 找出来？

如果鸡蛋足够多（大于等于 $\log_2 n$ 个），可以通过二分查找的方法来测试。如果鸡蛋不够多，可能二分查找过程中，鸡蛋就用没了，则不能通过二分查找的方法来测试。

那么这时候为了找出 f ，我们应该如何求出最少的扔鸡蛋次数？

思路 1：动态规划（超时）

可以这样考虑。题目限定了 n 层楼，k 个鸡蛋。

如果我们尝试在 1 ~ n 层中的任意一层 x 扔鸡蛋：

1. 如果鸡蛋没碎，则说明 1 ~ x 层都不用再考虑了，我们需要用 k 个鸡蛋去考虑剩下的 n - x 层，问题就从 (n, k) 转变为了 (n - x, k)。
2. 如果鸡蛋碎了，则说明 x + 1 ~ n 层都不用再考虑了，我们需要去剩下的 k - 1 个鸡蛋考虑剩下的 x - 1 层，问题就从 (n, k) 转变为了 (x - 1, k - 1)。

这样一来，我们就可以根据上述关系使用动态规划方法来解决这道题目了。具体步骤如下：

1. 划分阶段

按照楼层数量、剩余鸡蛋个数进行阶段划分。

2. 定义状态

定义状态 dp[i][j] 表示为：一共有 i 层楼，j 个鸡蛋的条件下，为了找出 f ，最坏情况下的最少扔鸡蛋次数。

3. 状态转移方程

根据之前的描述，dp[i][j] 有两个来源，其状态转移方程为：

$dp[i][j] = min_{1 \le x \le n} (max(dp[i - x][j], dp[x - 1][j - 1])) + 1$

4. 初始条件

给定鸡蛋 k 的取值范围为 [1, 100]，f 值取值范围为 [0, n]，初始化时，可以考虑将所有值设置为当前拥有的楼层数。

• 当鸡蛋数为 1 时，dp[i][1] = i。这是如果唯一的蛋碎了，则无法测试了。只能从低到高，一步步进行测试，最终最少测试数为当前拥有的楼层数（如果刚开始初始化时已经将所有值设置为当前拥有的楼层数，其实这一步可省略）。
• 当楼层为 1 时，在 1 层扔鸡蛋，dp[1][j] = 1。这是因为：
  • 如果在 1 层扔鸡蛋碎了，则 f < 1。同时因为 f 的取值范围为 [0, n]。所以能确定 f = 0。
  • 如果在 1 层扔鸡蛋没碎，则 f >= 1。同时因为 f 的取值范围为 [0, n]。所以能确定 f = 0。

5. 最终结果

根据我们之前定义的状态，dp[i][j] 表示为：一共有 i 层楼，j 个鸡蛋的条件下，为了找出 f ，最坏情况下的最少扔鸡蛋次数。则最终结果为 dp[n][k]。

思路 1：代码

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

        # for i in range(1, n + 1):
        #     dp[i][1] = i

        for j in range(1, k + 1):
            dp[1][j] = 1

        for i in range(2, n + 1):
            for j in range(2, k + 1):
                for x in range(1, i + 1):
                    dp[i][j] = min(dp[i][j], max(dp[i - x][j], dp[x - 1][j - 1]) + 1)
                
        return dp[n][k]

思路 1：复杂度分析

• 时间复杂度：$O(n^2 \times k)$。三重循环的时间复杂度为 $O(n^2 \times k)$。
• 空间复杂度：$O(n \times k)$。

思路 2：动态规划优化

上一步中时间复杂度为 $O(n^2 \times k)$。根据 $n$ 的规模，提交上去不出意外的超时了。

我们可以观察一下上面的状态转移方程：$dp[i][j] = min_{1 \le x \le n} (max(dp[i - x][j], dp[x - 1][j - 1])) + 1$ 。

这里最外两层循环的 i、j 分别为状态的阶段，可以先将 i、j 看作固定值。最里层循环的 x 代表选择的任意一层 x ，值从 1 遍历到 i。

此时我们把 dp[i - x][j] 和 dp[x - 1][j - 1] 分别单独来看。可以看出：

• 对于 dp[i - x][j]：当 x 增加时，i - x 的值减少，dp[i - x][j] 的值跟着减小。自变量 x 与函数 dp[i - x][j] 是一条单调非递增函数。
• 对于 dp[x - 1][j - 1]：当 x 增加时， x - 1 的值增加，dp[x - 1][j - 1] 的值跟着增加。自变量 x 与函数 dp[x - 1][j - 1] 是一条单调非递减函数。

两条函数的交点处就是两个函数较大值的最小值位置。即 dp[i][j] 所取位置。而这个位置可以通过二分查找满足 dp[x - 1][j - 1] >= dp[i - x][j] 最大的那个 x。这样时间复杂度就从 $O(n^2 \times k)$ 优化到了 $O(n \log n \times k)$。

思路 2：代码

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

        # for i in range(1, n + 1):
        #     dp[i][1] = i

        for j in range(1, k + 1):
            dp[1][j] = 1

        for i in range(2, n + 1):
            for j in range(2, k + 1):
                left, right = 1, i
                while left < right:
                    mid = left + (right - left) // 2
                    if dp[mid - 1][j - 1] < dp[i - mid][j]:
                        left = mid + 1
                    else:
                        right = mid
                dp[i][j] = max(dp[left - 1][j - 1], dp[i - left][j]) + 1
                    
        return dp[n][k]

思路 2：复杂度分析

• 时间复杂度：$O(n \log n \times k)$。两重循环的时间复杂度为 $O(n \times k)$，二分查找的时间复杂度为 $O(\log n)$。
• 空间复杂度：$O(n \times k)$。

思路 3：动态规划 + 逆向思维

再看一下我们现在的题目要求：已知有 n 层楼，k 个鸡蛋，求出至少需要扔几次鸡蛋，才能保证无论 f 是多少层，都能将 f 找出来？

我们可以逆向转换一下思维，将题目转变为：已知有 k 个鸡蛋，最多扔 x 次鸡蛋（碎没碎都算 1 次），求最多可以检测的多少层？

我们把未知条件「扔鸡蛋的次数」变为了已知条件，将「检测的楼层个数」变为了未知条件。

这样如果求出来的「检测的楼层个数」大于等于 n，则说明 1 ~ n 层楼都考虑全了，f 值也就明确了。我们只需要从符合条件的情况中，找出「扔鸡蛋次数」最少的次数即可。

动态规划的具体步骤如下：

1. 划分阶段

按照鸡蛋个数、扔鸡蛋的次数进行阶段划分。

2. 定义状态

定义状态 dp[i][j] 表示为：一共有 i 个鸡蛋，最多扔 j 次鸡蛋（碎没碎都算 1 次）的条件下，最多可以检测的楼层个数。

3. 状态转移方程

我们现在有 i 个鸡蛋，j 次扔鸡蛋的机会，现在尝试在 1 ~ n 层中的任意一层 x 扔鸡蛋：

1. 如果鸡蛋没碎，剩下 i 个鸡蛋，还有 j - 1 次扔鸡蛋的机会，最多可以检测 dp[i][j - 1] 层楼层。
2. 如果鸡蛋碎了，剩下 i - 1 个鸡蛋，还有 j - 1 次扔鸡蛋的机会，最多可以检测 dp[i - 1][j - 1] 层楼层。
3. 再加上我们扔鸡蛋的第 x 层，i 个鸡蛋，j 次扔鸡蛋的机会最多可以检测 dp[i][j - 1] + dp[i - 1][j - 1] + 1 层。

则状态转移方程为：$dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + 1$。

4. 初始条件

• 当鸡蛋数为 1 时，只有 1 次扔鸡蛋的机会时，最多可以检测 1 层，即 dp[1][1] = 1。

5. 最终结果

根据我们之前定义的状态，dp[i][j] 表示为：一共有 i 个鸡蛋，最多扔 j 次鸡蛋（碎没碎都算 1 次）的条件下，最多可以检测的楼层个数。则我们需要从满足 i == k 并且 dp[i][j] >= n（即 k 个鸡蛋，j 次扔鸡蛋，一共检测出 n 层楼）的情况中，找出最小的 j，将其返回。

思路 3：代码

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

        for i in range(1, k + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + 1
                if i == k and dp[i][j] >= n:
                    return j
        return n

思路 3：复杂度分析

• 时间复杂度：$O(n \times k)$。两重循环的时间复杂度为 $O(n \times k)$。
• 空间复杂度：$O(n \times k)$。

参考资料

• 【题解】题目理解 + 基本解法 + 进阶解法 - 鸡蛋掉落 - 力扣
• 【题解】动态规划（只解释官方题解方法一）（Java） - 鸡蛋掉落 - 力扣
• 【题解】动态规划 & 记忆化搜索 2000ms -> 32ms 的过程 - 鸡蛋掉落 - 力扣