lucifer

这是一道 LeetCode 难度为 Hard 的题目,很多大公司都会考,来看看。

原题地址:https://leetcode-cn.com/problems/super-egg-drop/

题目描述

你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。

你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?

示例 1:

输入:K = 1, N = 2
输出:2
解释:
鸡蛋从 1 楼掉落。如果它碎了,我们肯定知道 F = 0 。
否则,鸡蛋从 2 楼掉落。如果它碎了,我们肯定知道 F = 1 。
如果它没碎,那么我们肯定知道 F = 2 。
因此,在最坏的情况下我们需要移动 2 次以确定 F 是多少。
示例 2:

输入:K = 2, N = 6
输出:3
示例 3:

输入:K = 3, N = 14
输出:4

提示:

1 <= K <= 100
1 <= N <= 10000

前置知识

思路

本题也是 vivo 2020 年提前批的一个笔试题。时间一个小时,一共三道题,分别是本题,合并 k 个链表,以及种花问题。

这道题我在很早的时候做过,也写了题解。现在看来,思路没有讲清楚。没有讲当时的思考过程还原出来,导致大家看的不太明白。今天给大家带来的是 887.super-egg-drop 题解的重制版。思路更清晰,讲解更透彻,如果觉得有用,那就转发在看支持一下?OK,我们来看下这道题吧。

这道题乍一看很复杂,我们不妨从几个简单的例子入手,尝试打开思路。

假如有 2 个鸡蛋,6 层楼。 我们应该先从哪层楼开始扔呢?想了一会,没有什么好的办法。我们来考虑使用暴力的手段。


(图 1. 这种思路是不对的)

既然我不知道先从哪层楼开始扔是最优的,那我就依次模拟从第 1,第 2。。。第 6 层扔。每一层楼丢鸡蛋,都有两种可能,碎或者不碎。由于是最坏的情况,因此我们需要模拟两种情况,并取两种情况中的扔次数的较大值(较大值就是最坏情况)。 然后我们从六种扔法中选择最少次数的即可。


(图 2. 应该是这样的)

而每一次选择从第几层楼扔之后,剩下的问题似乎是一个规模变小的同样问题。嗯哼?递归?

为了方便描述,我将 f(i, j) 表示有 i 个鸡蛋, j 层楼,在最坏情况下,最少的次数。

伪代码:

1
2
3
4
5
6
def superEggDrop(K, N):
ans = N
# 暴力枚举从第 i 层开始扔
for i in range(1, N + 1):
ans = min(ans, max(self.superEggDrop(K - 1, i - 1) + 1, self.superEggDrop(K, N - i) + 1))
return ans

如上代码:

  • self.superEggDrop(K - 1, i - 1) 指的是鸡蛋破碎的情况,我们就只剩下 K - 1 个鸡蛋, 并且 i - 1 个楼层需要 check。
  • self.superEggDrop(K, N - i) + 1 指的是鸡蛋没有破碎的情况,我们仍然有 K 个鸡蛋, 并且剩下 N - i 个楼层需要 check。

接下来,我们增加两行递归的终止条件,这道题就完成了。

1
2
3
4
5
6
7
8
9
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
if K == 1: return N
if N == 0 or N == 1: return N
ans = N
# 暴力枚举从第 i 层开始扔
for i in range(1, N + 1):
ans = min(ans, max(self.superEggDrop(K - 1, i - 1) + 1, self.superEggDrop(K, N - i) + 1))
return ans

可是如何这就结束的话,这道题也不能是 hard,而且这道题是公认难度较大的 hard 之一。

上面的代码会 TLE,我们尝试使用记忆化递归来试一下,看能不能 AC。

1
2
3
4
5
6
7
8
9
10
11

class Solution:
@lru_cache()
def superEggDrop(self, K: int, N: int) -> int:
if K == 1: return N
if N == 0 or N == 1: return N
ans = N
# 暴力枚举从第 i 层开始扔
for i in range(1, N + 1):
ans = min(ans, max(self.superEggDrop(K - 1, i - 1) + 1, self.superEggDrop(K, N - i) + 1))
return ans

性能比刚才稍微好一点,但是还是很容易挂。

那只好 bottom-up(动态规划)啦。


(图 3)

我将上面的过程简写成如下形式:


(图 4)

与其递归地进行这个过程,我们可以使用迭代的方式。 相比于上面的递归式,减少了栈开销。然而两者有着很多的相似之处。

如果说递归是用函数调用来模拟所有情况, 那么动态规划就是用表来模拟。我们知道所有的情况,无非就是 N 和 K 的所有组合,我们怎么去枚举 K 和 N 的所有组合? 当然是套两层循环啦!


(图 5. 递归 vs 迭代)

如上,你将 dp[i][j] 看成 superEggDrop(i, j),是不是和递归是一摸一样?

来看下迭代的代码:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
for i in range(K + 1):
for j in range(N + 1):
if i == 1:
dp[i][j] = j
if j == 1 or j == 0:
dp[i][j] == j
dp[i][j] = j
for k in range(1, j + 1):
dp[i][j] = min(dp[i][j], max(dp[i - 1][k - 1] + 1, dp[i][j - k] + 1))
return dp[K][N]

值得注意的是,在这里内外循环的顺序无关紧要,并且内外循坏的顺序对我们写代码来说复杂程度也是类似的,各位客官可以随意调整内外循环的顺序。比如这样也是可以的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
dp = [[0] * (K + 1) for _ in range(N + 1)]

for i in range(N + 1):
for j in range( K + 1):
if j == 1:
dp[i][j] = i
if i == 1 or i == 0:
dp[i][j] == i
dp[i][j] = i
for k in range(1, i + 1):
dp[i][j] = min(dp[i][j], max(dp[k - 1][j - 1] + 1, dp[i - k][j] + 1))
return dp[N][K]
dp = [[0] * (N + 1) for _ in range(K + 1)]

总结一下,上面的解题方法思路是:

然而这样还是不能 AC。这正是这道题困难的地方。 一道题目往往有不止一种状态转移方程,而不同的状态转移方程往往性能是不同的。

那么这道题有没有性能更好的其他的状态转移方程呢?

把思路逆转!

这是《逆转裁判》 中经典的台词, 主角在深处绝境的时候,会突然冒出这句话,从而逆转思维,寻求突破口。

我们这样来思考这个问题。 既然题目要求最少的扔的次数,假设有一个函数 f(k, i),他的功能是求出 k 个鸡蛋,扔 i 次所能检测的最高楼层。

我们只需要不断进行发问:

  • ”f 函数啊 f 函数,我扔一次可以么?“, 也就是判断 f(k, 1) >= N 的返回值
  • ”f 函数啊 f 函数,我扔两次呢?“, 也就是判断 f(k, 2) >= N 的返回值
  • ”f 函数啊 f 函数,我扔 m 次呢?“, 也就是判断 f(k, m) >= N 的返回值

我们只需要返回第一个返回值为 true 的 m 即可。

想到这里,我条件发射地想到了二分法。 聪明的小朋友们,你们觉得二分可以么?为什么?欢迎评论区留言讨论。

那么这个神奇的 f 函数怎么实现呢?其实很简单。

  • 摔碎的情况,可以检测的最高楼层是f(m - 1, k - 1) + 1。因为碎了嘛,我们多检测了摔碎的这一层。
  • 没有摔碎的情况,可以检测的最高楼层是f(m - 1, k)。因为没有碎,也就是说我们啥都没检测出来(对能检测的最高楼层无贡献)。

我们来看下代码:

1
2
3
4
5
6
7
8
9
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
def f(m, k):
if k == 0 or m == 0: return 0
return f(m - 1, k - 1) + 1 + f(m - 1, k)
m = 0
while f(m, K) < N:
m += 1
return m

上面的代码可以 AC。我们来顺手优化成迭代式。

1
2
3
4
5
6
7
8
9
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
dp = [[0] * (K + 1) for _ in range(N + 1)]
m = 0
while dp[m][K] < N:
m += 1
for i in range(1, K + 1):
dp[m][i] = dp[m - 1][i - 1] + 1 + dp[m - 1][i]
return m

代码

代码支持:JavaSCript,Python

Python:

1
2
3
4
5
6
7
8
9
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
dp = [[0] * (K + 1) for _ in range(N + 1)]
m = 0
while dp[m][K] < N:
m += 1
for i in range(1, K + 1):
dp[m][i] = dp[m - 1][i - 1] + 1 + dp[m - 1][i]
return m

JavaSCript:

1
2
3
4
5
6
7
8
9
10
11
12
13
var superEggDrop = function (K, N) {
// 不选择dp[K][M]的原因是dp[M][K]可以简化操作
const dp = Array(N + 1)
.fill(0)
.map((_) => Array(K + 1).fill(0));

let m = 0;
while (dp[m][K] < N) {
m++;
for (let k = 1; k <= K; ++k) dp[m][k] = dp[m - 1][k - 1] + 1 + dp[m - 1][k];
}
return m;
};

复杂度分析

  • 时间复杂度:$O(m * K)$,其中 m 为答案。
  • 空间复杂度:$O(K * N)$

对为什么用加法的同学有疑问的可以看我写的《对《丢鸡蛋问题》的一点补充》

总结

  • 对于困难,先举几个简单例子帮助你思考。
  • 递归和迭代的关系,以及如何从容地在两者间穿梭。
  • 如果你还不熟悉动态规划,可以先从递归做起。多画图,当你做多了题之后,就会越来越从容。
  • 对于动态规划问题,往往有不止一种状态转移方程,而不同的状态转移方程往往性能是不同的。

友情提示: 大家不要为了这个题目高空抛物哦。

更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 30K star 啦。

大家也可以关注我的公众号《力扣加加》获取更多更新鲜的 LeetCode 题解


 评论


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 。
载入天数...载入时分秒...