题目
假设有个鸡蛋和层楼,每个蛋的性质完全相同,而且如果某个蛋已经碎了,就没法再次使用。假如存在楼层,且鸡蛋从任何高于的楼层扔下都会碎掉,但从低于或等于的楼层扔下则不会碎。
每次移动,都可以使用一个鸡蛋从某个楼层扔下,如果你想准确地测得的值,那么在最坏的情况下,最少需要移动几次?
原题链接:Leetcode 887。
题解
刚看到这道题时,很容易一头雾水,不知道题目在说些什么,因为扔鸡蛋的结果我们是无法在做题时实时获得的,比如我们在第层楼扔第个蛋时,是不知道这个蛋是否会碎,而且对于给定楼层总数和鸡蛋总数,我们知道存在楼层会令鸡蛋碎掉,但是我们却并不知道这个数值到底是几。
那么这道题到底在说些什么呢?经过分析可以发现,这道题之所以难理解,是因为题目将真正考察的地方隐藏起来了,题目的核心就在于理解最后一句话:在最坏的情况下,最少移动几次。这句话意味着,我们在扔鸡蛋时是可以采取多种策略的,每种策略都对应一种最坏情况,比如:
- 采用策略:从第一层逐层向上扔,那么最坏情况是;
- 采用策略:从顶楼逐层向下扔,那么最坏情况是,即与第一种策略类似;
- 采用最优策略,我们现在可能不知道这个策略具体是什么,但是可以确定移动次数是。
针对上面列出的几种情况,不难发现,移动次数是与有关的函数,即,那么函数就可以代表我们选择的策略,由于具体的策略我们是不知道的,所以将策略函数也看作一个变量,那么最终我们要求得的表达式可以写作:
到了这一步,我们才算是真正的理解题意了,我们需要找到一个算法,在策略空间中找到最优策略,并且针对这种策略,找到最坏情况F\in\[0,N]对应的。
绕了这么久,可以发现,我们遍历所有可能的策略,并且在每个策略中,都假设楼层总是出现在使当前策略移动次数最大的楼层处,题目并没有给出如何遍历楼层,也没有给出的值,这两个值都需要我们在算法中自行遍历。
对于这个问题,一个自然的思路就是使用动态规划的思想来处理。我们使用状态表来表示我们拥有个鸡蛋和层楼时的最小移动次数,那么考虑初始情况,拥有个蛋,层楼时:
- 若,毋庸置疑,不需要进行测试,因为没有鸡蛋和楼层,;
- 若,此时我们只有一个蛋,那么只能使用前面提到的策略来试探,那么最坏情况就是,即蛋碎的楼层在最大楼层处,那么我们最少尝试次数就是;
- 若,我们有不止一个鸡蛋,但是只有一层楼,那么毫无疑问,只需要测试一次就行了,得到;
- 若,即有不止一个鸡蛋,且不止一层楼,那么我们就需要使用最优策略来确定最小移动次数,
写成代码形式:
def superEggDrop(self, K: int, N: int) -> int:
dp = [[0] * (K + 1) for i in range(N + 1)]
for i in range(1, N + 1): dp[i][1] = i
for i in range(1, K + 1): dp[1][i] = 1
for i in range(2, N + 1):
for j in range(2, K + 1):
dp[i][j] = dp[i][j - 1]
for k in range(1, i + 1):
dp[i][j] = min(dp[i][j], 1 + max(dp[k - 1][j - 1], dp[i - k][j]))
return dp[N][K]
算法复杂度:
查看带有公式渲染的博客内容:https://blog.simplenaive.cn/#/post/20