Skip to content

Latest commit

 

History

History
348 lines (247 loc) · 12.3 KB

887.super-egg-drop.md

File metadata and controls

348 lines (247 loc) · 12.3 KB
Raw

题目地址(887. 鸡蛋掉落)

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，我们来看下这道题吧。

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

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

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

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

（图1）

而每一次选择从第几层楼扔之后，剩下的问题似乎是一个规模变小的同样问题。比如选择从 i 楼扔，如果碎了，我们需要的答案就是 1 + f(k-1, i-1)，如果没有碎，需要在找 [i+1, n]，这其实等价于在 [1,n-i]中找。我们发现可以将问题转化为规模更小的子问题，因此不难想到递归来解决。

伪代码：

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。

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

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。

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（动态规划）啦。

(图 2)

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

(图 3)

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

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

（图 4. 递归 vs 迭代）

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

来看下迭代的代码：

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[i for _ in range(K+1)] for i in range(N + 1)]
        for i in range(N + 1):
            for j in range(1, K + 1):
                dp[i][j] = i
                if j == 1:
                    continue
                if i == 1 or i == 0:
                    break
                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]

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

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[i for i in range(N+1)] for _ in range(K + 1)]
        for i in range(1, K + 1):
            for j in range(N + 1):
                dp[i][j] = j
                if i == 1:
                    break
                if j == 1 or j == 0:
                    continue
                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]

总结一下，上面的解题方法思路是：

(图 5)

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

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

把思路逆转！

(图 6)

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

我们这样来思考这个问题。 既然题目要求最少的扔的次数，假设有一个函数 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 即可。由于 m 不会大于 N，因此时间复杂度也相对可控。这么做的好处就是不用思考从哪里开始扔，扔完之后下一次从哪里扔。

对于这种二段性的题目应该想到二分法，如果你没想起来，请先观看我的仓库里的二分专题哦。实际上不二分也完全可以通过此题目，具体下方代码，有实现带二分的和不带二分的。

最后剩下一个问题。这个神奇的 f 函数怎么实现呢？

  • 摔碎的情况，可以检测的最大楼层数是f(m - 1, k - 1)。也就是说，接下来我们需要往下找，最多可以找 f(m-1, k-1) 层
  • 没有摔碎的情况，可以检测的最大楼层数是f(m - 1, k)。也就是说，接下来我们需要往上找，最多可以找 f(m-1, k) 层

也就是当前扔的位置上面可以有 f(m-1, k) 层，下面可以有 f(m-1, k-1) 层，这样无论鸡蛋碎不碎，我都可以检测出来。因此能检测的最大楼层数就是向上找的最大楼层数+向下找的最大楼层数+1，其中 1 表示当前层，即 f(m - 1, k - 1) + f(m - 1, k) + 1

首先我们来看下二分代码：

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        @cache
        def f(m, k):
            if k == 0 or m == 0: return 0
            return f(m - 1, k - 1) + 1 +  f(m - 1, k)
        l, r = 1, N
        while l <= r:
            mid = (l + r) // 2
            if f(mid, K) >= N:
                r = mid - 1
            else:
                l = mid + 1
            
        return l

下面代码区我们实现不带二分的版本。

代码

代码支持：Python, CPP, Java, JavaSCript

Python:

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[0] * (N + 1) for _ in range(K + 1)]
        
        for m in range(1, N + 1):
            for k in range(1, K + 1):
                dp[k][m] = dp[k - 1][m - 1] + 1 + dp[k][m - 1]
                if dp[k][m] >= N:
                    return m
        
        return N  # Fallback, should not reach here

CPP:

#include <vector>
#include <functional>

class Solution {
public:
    int superEggDrop(int K, int N) {
        std::vector<std::vector<int>> dp(K + 1, std::vector<int>(N + 1, 0));
        
        for (int m = 1; m <= N; ++m) {
            for (int k = 1; k <= K; ++k) {
                dp[k][m] = dp[k - 1][m - 1] + 1 + dp[k][m - 1];
                if (dp[k][m] >= N) {
                    return m;
                }
            }
        }
        
        return N; // Fallback, should not reach here
    }
};

Java:

import java.util.Arrays;

class Solution {
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K + 1][N + 1];
        
        for (int m = 1; m <= N; ++m) {
            for (int k = 1; k <= K; ++k) {
                dp[k][m] = dp[k - 1][m - 1] + 1 + dp[k][m - 1];
                if (dp[k][m] >= N) {
                    return m;
                }
            }
        }
        
        return N; // Fallback, should not reach here
    }
}

JavaSCript:

/**
 * @param {number} k
 * @param {number} n
 * @return {number}
 */
var superEggDrop = function superEggDrop(K, N) {
    const dp = Array.from({ length: K + 1 }, () => Array(N + 1).fill(0));
    
    for (let m = 1; m <= N; ++m) {
        for (let k = 1; k <= K; ++k) {
            dp[k][m] = dp[k - 1][m - 1] + 1 + dp[k][m - 1];
            if (dp[k][m] >= N) {
                return m;
            }
        }
    }
    
    return N; // Fallback, should not reach here
}

复杂度分析

  • 时间复杂度：$O(N * K)$
  • 空间复杂度：$O(N * K)$

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

总结

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

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

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

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