对《丢鸡蛋问题》的一点补充

​ 去年的一年时间，我在群里每天都会出题给大家做。但是就在 2020-03 开始，力扣也开展了每日一题活动。我突然觉得这个每日一题的必要性变得小了很多，并且逐渐减少了出题频率。但是我还是不愿意放弃大家一起集中进行交流学习的机会。于是我打算新开辟一个专题，这个专题一方面要和力扣官方的每日一题重合度低，另一方面要让大家有参与的热情。

于是【异议！】系列应运而生。它是个什么东西呢？我相信大家一定在平时刷算法的过程中，一定遇到过“这解法怎么想到的？”，“这解法不对吧？”的情况，并且可悲的是没有人能够回答你。来这里，「力扣加加」 来回答你。我们会对大家提出的问题进行筛选，将有意义的问题开放出来给大家讨论和学习。

本次给大家带来的/是【异议！】系列「第二弹」。

​

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

事情的起源

昨天有人在我的力扣题解下留言，问我《丢鸡蛋问题》重制版来袭～》题解中为什么第二种算法是加法而不是 min 什么的。毕竟我的第一种算法可是 min(max(碎, 不碎))，为什么第二种就是加法了呢？这个细节我在写题解的时候漏掉了，我打算详细给大家说一下。

题目描述

你将获得 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

我当时的解法

我们这样来思考这个问题。 既然题目要求最少的扔的次数，假设有一个函数 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)。因为没有碎，也就是说我们啥都没检测出来（对能检测的最高楼层无贡献）。

我们来看下代码：

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。我们来顺手优化成迭代式。

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:

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:

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)$

为什么是加法

在解法一种我提到了：算法一的本质就是暴力地枚举所有的可能楼层，然后比较最坏情况下的最少扔鸡蛋次数。而实际上解法二也是基于这个大前提，假设我们选择一个楼层是 x。那么在 x 层扔鸡蛋会有两种可能：

• 鸡蛋碎了。 说明目标楼层 F 就是本层或者比本层低，楼上的 N - x 层不需要检测了，全部排除了。因此我们需要继续探测楼下 x - 1 层，而我们剩下可以探测的最高楼层为 dp[k - 1][m - 1]。由于我们需要探测到具体的 F，因此我们需要使得 dp[k - 1][m - 1] >= x - 1。
• 鸡蛋没碎。 说明目标楼层 F 比本层高，楼下的 x - 1 不需要检测了，全部排除了。因此我们需要继续探测楼上 N - x 层，而我们剩下可以探测的最高楼层为 dp[k][m - 1]。由于我们需要探测到具体的 F，因此我们需要使得 dp[k][m - 1] >= N - x。

无论鸡蛋碎还是不碎，我们都只需要检测上面或者检测下面，不需要同时检测。

也就是说我需要找到一个楼层 x， 使得 x 同时满足：

1. dp[k - 1][m - 1] >= x - 1
2. dp[k][m - 1] >= N - x

这样能保证 100% 可以检测出来目标楼层 F。实际上不管鸡蛋碎不碎，可以检测的楼层都是 max(dp[k - 1][m - 1], x -1) + max(dp[k][m - 1], N -x) + 1，由于 dp[k - 1][m - 1] >= x - 1，dp[k][m - 1] >= N - x，因此可以检测的楼层就是 dp[k - 1][m - 1] + dp[k][m - 1] + 1。

这个我可能需要解释一下。 由于选择 x 开始扔之前已经确定了上面的两个不等式是成立的了，因此如果鸡蛋没碎，我们需要继续往上检测，下面是不需要检测的，虽然下面是 x - 1，但是为了保证万一碎的情况也有解，所以有 dp[k - 1][m - 1] >= x - 1，因此实际上可以确定的最大楼层是 dp[k][m - 1] + max(dp[k - 1][m - 1], x -1) + 1，也就是 dp[k][m - 1] + dp[k - 1][m - 1] + 1。鸡蛋如果碎的情况也是一样的分析逻辑。

大家对这道题还有任何问题，都可以留言告诉我！

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

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。