扔鸡蛋问题

这是一道非常经典的google面试题，在此记录一下。

具体案例引导可见：扔鸡蛋问题（四种解法）

思路

这里介绍动态规划的解法：

我们假设 $F(K,N)$ 表示有 $K$ 个鸡蛋、$N$ 层楼，测出其摔碎临界点所需的最少次数，那么有如下状态转移公式：

$$F(K, N) = 1 + min_{1 \leq i \leq N} max(F(K, N-i), F(K-1, i-1))$$

• $F(K, N-i)$ : 如果第一个鸡蛋在第 $i$ 层没有摔碎，那么我们还有 $K$ 个鸡蛋以及剩余 $N-i$ 个楼层测试
• $F(K-1, i-1)$ : 如果第一个鸡蛋在第 $i$ 层摔碎，那么我们还有 $K-1$ 个鸡蛋以及剩余 $i-1$ 个楼层测试
• 取两者最坏情况，再取所有情况中最小的值，表示最少测试次数。

代码

具体编程实现如下：

class Solution:

    def superEggDrop(self, K: int, N: int) -> int:
        dp = [ [0]*(N+1) for _ in range(K+1) ]
        for i in range(1, N+1):
            dp[1][i] = i
        
        for k in range(2, K+1):
            for n in range(1, N+1):
                min_drop = N
                for i in range(1, N+1):
                    tmp_max = max(dp[k-1][i-1], dp[k][n-i])
                    min_drop = min(min_drop, 1+tmp_max)
                dp[k][n] = min_drop
        return dp[K][N]

上述代码在leetcode上超时了，复制粘贴了官方的代码ac的。

---

参考

• 887. 鸡蛋掉落
• 扔鸡蛋问题
• 扔鸡蛋问题（四种解法）