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
2
3
输入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:代码 #

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

这里最外两层循环的 ij 分别为状态的阶段,可以先将 ij 看作固定值。最里层循环的 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:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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)$。

参考资料 #

本站总访问量  次  |  您是本站第  位访问者