0887. 鸡蛋掉落
0887. 鸡蛋掉落
- 标签：数学、二分查找、动态规划
- 难度：困难
题目链接
题目大意
描述：给定一个整数 k 和整数 n，分别代表 k 枚鸡蛋和可以使用的一栋从第 1 层到第 n 层楼的建筑。
已知存在楼层 f，满足 0 <= f <= n，任何从高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会碎。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n），如果鸡蛋碎了，就不能再次使用它。如果鸡蛋没碎，则可以再次使用。
要求：计算并返回要确定 f 确切值的最小操作次数是多少。
说明：
- 。
- 。
示例：
- 示例 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楼不碎，再去2楼扔。 2楼还不碎，就去3楼扔。- ……
- 直到鸡蛋碎了，也就找到了鸡蛋不会摔碎的最高层
f。
用这种方法，最坏情况下，鸡蛋在第 n 层也没摔碎。这种情况下我们总共试了 n 次才确定鸡蛋不会摔碎的最高楼层 f。
下面再来说一下比 n 次要少的情况。
如果我们可以通过二分查找的方法，先从 1 ~ n 层的中间层开始扔鸡蛋。
- 如果鸡蛋碎了，则从第
1层到中间层这个区间中去扔鸡蛋。 - 如果鸡蛋没碎，则从中间层到第
n层这个区间中去扔鸡蛋。
每次扔鸡蛋都从区间的中间层去扔，这样每次都能排除当前区间一半的答案，从而最终确定鸡蛋不会摔碎的最高楼层 f。
通过这种二分查找的方法，可以优化到 次就能确定鸡蛋不会摔碎的最高楼层 f。
因为 ，所以通过二分查找的方式，「至少」比线性查找的次数要少。
同样，我们还可以通过三分查找、五分查找等等方式减少次数。
这是在不限制鸡蛋个数的情况下，现在我们来限制一下鸡蛋个数为 k。
现在题目要求：已知有 n 层楼，k 个鸡蛋，求出至少需要扔几次鸡蛋，才能保证无论 f 是多少层，都能将 f 找出来？
如果鸡蛋足够多（大于等于 个），可以通过二分查找的方法来测试。如果鸡蛋不够多，可能二分查找过程中，鸡蛋就用没了，则不能通过二分查找的方法来测试。
那么这时候为了找出 f ，我们应该如何求出最少的扔鸡蛋次数？
思路 1：动态规划（超时）
可以这样考虑。题目限定了 n 层楼，k 个鸡蛋。
如果我们尝试在 1 ~ n 层中的任意一层 x 扔鸡蛋：
- 如果鸡蛋没碎，则说明
1~x层都不用再考虑了，我们需要用k个鸡蛋去考虑剩下的n - x层，问题就从(n, k)转变为了(n - x, k)。 - 如果鸡蛋碎了，则说明
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] 有两个来源，其状态转移方程为：
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：复杂度分析
- 时间复杂度：。三重循环的时间复杂度为 。
- 空间复杂度：。
思路 2：动态规划优化
上一步中时间复杂度为 。根据 的规模，提交上去不出意外的超时了。
我们可以观察一下上面的状态转移方程： 。
这里最外两层循环的 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。这样时间复杂度就从 优化到了 。
思路 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：复杂度分析
- 时间复杂度：。两重循环的时间复杂度为 ，二分查找的时间复杂度为 。
- 空间复杂度：。
思路 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 扔鸡蛋：
- 如果鸡蛋没碎，剩下
i个鸡蛋，还有j - 1次扔鸡蛋的机会，最多可以检测dp[i][j - 1]层楼层。 - 如果鸡蛋碎了，剩下
i - 1个鸡蛋，还有j - 1次扔鸡蛋的机会，最多可以检测dp[i - 1][j - 1]层楼层。 - 再加上我们扔鸡蛋的第
x层，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：复杂度分析
- 时间复杂度：。两重循环的时间复杂度为 。
- 空间复杂度：。