双蛋问题以及更主要的其更通用化且有用的问题的解

题目：LeetCode 887. 鸡蛋掉落

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

思路

基本想法

首先，我们可以看到要得到较大的楼层和鸡蛋的答案，小的情况下的结果是有用的分析，这就导致了动态递推。

定义子问题，也就是定义子状态。

我们有两个变量

还有多少可以扔的鸡蛋 i ，(0 <= i <= K)
还剩下几层楼来测试 j ，(i <= j <= N)

结果就是我们子问题

dp[i][j]就是在还有i个鸡蛋，j层楼的时候，我们要得到这个目标楼层所用的最小次数。

DP方程

初始化

1
2
3

dp[1][j] = j, j = 1...N # one egg, check each floor from 1 to j
dp[i][0] = 0, i = 1...K # no floor, no drop needed to get the optimal floor
dp[i][1] = 1, i = 1...K # one floor, only check once

递推方程

为了得到递归关系，我们来考虑一个测试案例。3个鸡蛋和100层楼对于写一次降落，我可以从1到100中选择楼层，比如我选择25。这个掉落有2种可能的结果。

蛋碎了，我现在有2个蛋，可以选择的楼层变成了1~24。
鸡蛋仍然安全，我仍然有3个鸡蛋，要选择的楼层变成26~100。

考虑最坏的情况，用上面的dp定义，我们可以把下一次选择楼层25的情况找目标楼层的情况描述成：

dp[3][100] = 1 + max(dp[2][24], dp[3][75])

除了第25层，对于下次抛下，我们也可以选择1到100层其他楼层。每一次抛下都类似于25层的情况。最终的结果将是所有这些可能的下次抛下的楼层的选择的最小值。

dp[3] [100] = min(..., 1 + max(dp[2] [23], dp[3] [76]), 1 + max(dp[2] [24], dp[3] [75]), 1 + max(dp[2] [25], dp[3] [74]), ...) (拿24、25、26举例)

最终的递推方程是： \[ dp[i] [j] = 1 + min(max(dp[i-1] [k-1], dp[i] [j-k]))， k = 1, 2, ...，j \]

暴力解法：

有了刚才的递推公式，暴力解法应该是O(kn^2)时间复杂度

示例代码：

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[float('inf')] * (N + 1) for _ in range(K + 1)]
        for i in range(1, K + 1):
            dp[i][0] = 0
            dp[i][1] = 1
        for j in range(1, N + 1):
            dp[1][j] = j

        for i in range(2, K + 1):
            for j in range(2, N + 1):
                for k in range(1, j + 1):
                    dp[i][j] = min(dp[i][j],
                                   1 + max(dp[i - 1][k - 1], dp[i][j - k]))
        return dp[K][N]

或者减少空间复杂度的下面代码

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = list(range(N + 1))
        _dp = [0] * (N + 1)
        for _ in range(K - 1):
            for j in range(1, N + 1):
                _dp[j] = 1 + min(max(dp[k - 1], _dp[j - k])
                                 for k in range(1, j + 1))
            dp, _dp = _dp, dp
        return dp[N]

优化1，对每个dp[i] [j]选择k

我们的暴力解法在leetcode上超时了，提示我们要检查for循环中不必要的迭代。更具体的说，为了得到每次抛下最适合的k值，我们不需要遍历从i到j的所有楼层， dp[i] [k]是一个随k的升高而升高的函数。这意味着dp[i-1] [k-1]将会升高而dp[i] [j-k]将会降低，当k从1到j的时候。最优的k值将在中点这两个值相遇的时候。所以为了得到最优的k值，我们可以对k从1到j做一个二分搜索。

这将使得第三个对k循环从O(n)的时间复杂度下降到O(logn)。总时间复杂度是O(knlogn)。使用二分搜索，我们只能做自底向上的dp，示例代码如下：

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        def dfs(i, j):
            if i == 1:
                return j
            if j == 0:
                return 0
            if j == 1:
                return 1
            if (i, j) in d:
                return d[i, j]
            lo, hi = 0, j
            while lo < hi:
                mid = (lo + hi) / 2
                left, right = dfs(i - 1, mid - 1), dfs(i, j - mid)
                if left < right:
                    lo = mid + 1
                else:
                    hi = mid
            res = 1 + max(dfs(i - 1, lo - 1), dfs(i, j - lo))
            d[i, j] = res
            return res

        d = {}
        return dfs(K, N)

优化2，为每个dp[i] [1..N] 选择 k_1 .. k_N

再进一步，到现在为止，我们仍然在为了每个dp[i] [j]寻找从1到j的最优层数k。事实上，我们可以看到，随着j的增加，每个dp[i] [j]的最优楼层k也在增加。这意味着一旦我们得到了dp[i] [j]的最优k，我们就可以保存当前k值，直接开始下一轮的for-loop，而不用再从0开始启动k。这样，在第三个for-loop中，由于j在第二个for-loop中从1到N，k只会从1到N一次，总的时间复杂度为O(kN)。代码如下所示：

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[float('inf')] * (N + 1) for _ in range(K + 1)]
        for i in range(1, K + 1):
            dp[i][0] = 0
            dp[i][1] = 1
        for j in range(1, N + 1):
            dp[1][j] = j

        for i in range(2, K + 1):
            k = 1
            for j in range(2, N + 1):
                while k < j + 1 and dp[i][j - k] > dp[i - 1][k - 1]:
                    k += 1
                dp[i][j] = 1 + dp[i - 1][k - 1]
        return dp[K][N]

优化3，空间复杂度

通常情况下，如果dp的递归关系是基于之前状态的恒定长度，我们可以节省一个维度的空间复杂度。在这里，当前行dp[i]是基于当前行和前行得到更新的，所以我们可以只记录这两行，并在迭代过程中进行更新，以节省一维的空间复杂度。最终时间复杂度O(kn)，空间复杂度O(n)。代码如下所示：

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = range(N + 1)
        for i in range(2, K + 1):
            k = 1
            ndp = [0, 1] + [float('inf')] * (N - 1)
            for j in range(2, N + 1):
                while k < j + 1 and ndp[j - k] > dp[k - 1]:
                    k += 1
                ndp[j] = 1 + dp[k - 1]
            dp = ndp
        return dp[N]

优化代码：

# f(i, j)还剩i个鸡蛋，k层楼，最少需要的次数
# 距离f(2, 100) 2个鸡蛋100层楼
# 选了25层，碎了，没碎
#        max(f(i-1, k-1) , f(i, j-k))
# f(i, j) = min(max(f(i-1, k-1), f(i, j-k))) + 1 for k in 1..j
# 初始化和边界条件
# f(i,1) = 1,一层只需要一次，只要鸡蛋数大于等于1
# f(1,j) = j,一个鸡蛋只能从最低层一个一个实验
# 层数加上一个哨兵0，这样访问索引即是层数，并且当k等于1时，递推到f(i, 0)为0
# 在一层碎了，f(i, 0) = 0
# 返回值，f(K,N)
# 优化复杂度
# 我们的k不用从1开始，随着j的增加，最合适的k层也是在增加的，对于每一个i，我们都重新开始计k
# 在这一轮中，k从上一次最佳开始，最佳的时候f(i-1, k-1) >= f(i, j-k)
# 我们取f(i-1, k-1)，更新f(i, j) = f(i-1,k-1)+1
# 可降低时间复杂度为O(KN)
# 空间复杂度，我们可以使用两个数组滚动
# 一个代表i-1个鸡蛋时，一个表示i个鸡蛋时
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = list(range(N + 1))
        ndp = [0] * (N + 1)
        for i in range(2, K + 1):
            k = 1
            for j in range(1, N + 1):
                while k <= j and dp[k - 1] < ndp[j - k]:
                    k += 1
                ndp[j] = dp[k - 1] + 1
            dp, ndp = ndp, dp
        return dp[N]

总结

我个人建议按照以下逻辑来思考这个问题。

为什么要用dp？在什么情况下我们应该用dp来解决问题？
问题中描述一个状态的基本情况和递归关系是什么？
根据以上分析，dp公式是什么？
实现蛮力解决。
优化：找到dp数组的模式，哪些迭代是不必要的，可以节省的？
时间和空间复杂度是多少？有什么办法可以节省一个维度的空间复杂度？

转载感谢

感谢优秀题解

https://leetcode.com/problems/super-egg-drop/discuss/159079/Python-DP-from-kn2-to-knlogn-to-kn