LeetCode困难题赏 - 887.扔鸡蛋

[Yidadaa]

题目

假设有$K$个鸡蛋和$N$层楼，每个蛋的性质完全相同，而且如果某个蛋已经碎了，就没法再次使用。假如存在楼层$F, F\in[0, n]$，且鸡蛋从任何高于$F$的楼层扔下都会碎掉，但从低于或等于$F$的楼层扔下则不会碎。

每次移动，都可以使用一个鸡蛋从某个楼层扔下，如果你想准确地测得$F$的值，那么在最坏的情况下，最少需要移动几次？

原题链接：Leetcode 887。

题解

刚看到这道题时，很容易一头雾水，不知道题目在说些什么，因为扔鸡蛋的结果我们是无法在做题时实时获得的，比如我们在第$x$层楼扔第$i$个蛋时，是不知道这个蛋是否会碎，而且对于给定楼层总数和鸡蛋总数，我们知道存在楼层$F$会令鸡蛋碎掉，但是我们却并不知道这个数值到底是几。

那么这道题到底在说些什么呢？经过分析可以发现，这道题之所以难理解，是因为题目将真正考察的地方隐藏起来了，题目的核心就在于理解最后一句话：在最坏的情况下，最少移动几次。这句话意味着，我们在扔鸡蛋时是可以采取多种策略的，每种策略都对应一种最坏情况，比如：

1. 采用策略$a$：从第一层逐层向上扔，那么最坏情况是$min(K, N, F)$；
2. 采用策略$b$：从顶楼逐层向下扔，那么最坏情况是$min(K, N, F)$，即与第一种策略类似；
3. 采用最优策略$\hat{f}$，我们现在可能不知道这个策略具体是什么，但是可以确定移动次数是$x=f(K, N, F)$。

针对上面列出的几种情况，不难发现，移动次数$x$是与$K, N, F$有关的函数，即$f(K, N, F)$，那么函数$f$就可以代表我们选择的策略，由于具体的策略我们是不知道的，所以将策略函数$f$也看作一个变量，那么最终我们要求得的$x$表达式可以写作：
$$x=g(K, N, F, f)$$
到了这一步，我们才算是真正的理解题意了，我们需要找到一个算法$g$，在策略空间$f\in\Psi$中找到最优策略$\hat{f}$，并且针对这种策略$\hat{f}$，找到最坏情况$F\in[0,N]$对应的$x$。

绕了这么久，可以发现，我们遍历所有可能的策略，并且在每个策略中，都假设楼层$F$总是出现在使当前策略$f$移动次数最大的楼层处，题目并没有给出如何遍历楼层，也没有给出$F$的值，这两个值都需要我们在算法$g$中自行遍历。

对于这个问题，一个自然的思路就是使用动态规划的思想来处理。我们使用状态表$dp[K][N]$来表示我们拥有$K$个鸡蛋和$N$层楼时的最小移动次数，那么考虑初始情况，拥有$i\in[0,K]$个蛋，$j\in[0,N]$层楼时：

1. 若$i=0 or j=0$，毋庸置疑，不需要进行测试，因为没有鸡蛋和楼层，$dp[0][1]=dp[1][0]=dp[0][0]=0$；
2. 若$i=1, j\in[1,N]$，此时我们只有一个蛋，那么只能使用前面提到的策略$a$来试探，那么最坏情况就是$F=j$，即蛋碎的楼层在最大楼层处，那么我们最少尝试次数就是$dp[1][j]=j, j\in[1,N]$；
3. 若$i\in(1,K], j=1$，我们有不止一个鸡蛋，但是只有一层楼，那么毫无疑问，只需要测试一次就行了，得到$dp[i][1]=1, i\in(1, K)$；
4. 若$i\in(1,K], j\in(1,N)$，即有不止一个鸡蛋，且不止一层楼，那么我们就需要使用最优策略$\hat{f}$来确定最小移动次数，

写成代码形式：

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]

算法复杂度：$O(KN^2)$

查看带有$\LaTeX$公式渲染的博客内容：https://blog.simplenaive.cn/#/post/20