leetcode-887-鸡蛋掉落（包含最大值最小化，最小值最大化的二分优化+滚动数组的原理）_dp 最大值最小化 最小值最大化

题意

链接：leetcode-887-鸡蛋掉落
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 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

解题

KNN复杂度DP解法思想（超时）

• 表示： dp[i][j]: 表示i个鸡蛋，j层楼的最少移动次数
• 初始状态： dp[0][:] = dp[:][0]=0, dp[1][h]=h(h从1层到n层：很好理解，1个鸡蛋h层,只能从1层慢慢往上试错)
• 状态转移： 考虑dp(i, j):i个鸡蛋j层需要最少移动多少次数，那么i个鸡蛋我们考虑从k层仍（k在1~j层）,dp(i, j) ----- dp(i, [1~k，k层, k~j])
  要么鸡蛋碎了，要么鸡蛋不碎
  如果碎了，说明鸡蛋破碎的界限f在1~k-1层，我们就不考虑k到j层了，此时鸡蛋碎了一个还有i-1个鸡蛋，所以变成了求i-1个鸡蛋k-1层最少移动多少次
  如果没碎，说明鸡蛋破碎的界限f在k+1~j层，我们就不考虑1到k层了，此时鸡蛋没碎还有i个鸡蛋，所以变成了求i个鸡蛋j-k层最少移动多少次

for j in range(1, n+1):
   res = float("INF")
   for h in range(1, j+1):
       res = min(res, max(dp[i][j-h], dp[i-1][h-1])+1)
       #加1是因为我们人了一次，进行了一次尝试
   dp[i][j] = res
1
2
3
4
5
6

上述方法的优化 （最大值最小化二分优化）

res = min(res, max(dp[i][j-h], dp[i-1][h-1])+1)
1

这是一个最大值最小化问题，可以用二分查找
首先明确一点，dp[i]这一层的值是一个递增的序列dp[i][j] <= dp[i][j+c] (c>0)

• 针对j-h, h是从1~j, 所以dp[i][j-h] 1<=h<=j,是一个递减的序列
• 针对h-1, h是从1~j, 所以dp[i][h-1] 1<=h<=j,是一个递增的序列
• 递减的序列就是dp[i][j-h], 递增的序列就是dp[i-1][h-1]，横轴是h的取值

• 那么max(dp[i][j-h], dp[i-1][h-1])是什么呢？显然是红框的部分
  
• 那么min(max(dp[i][j-h], dp[i-1][h-1]))是什么呢，显然是这个最低点，既然h从1~j遍历，从这图清晰看出可以使用二分查找，如果

• 如果dp[i][j-mid]>dp[i-1][mid-1], 就是左边的虚线情况，说明最低点在mid右边
• 如果dp[i][j-mid]<dp[i-1][mid-1], 就是右边的虚线情况，说明最低点在mid左边
• 很符合二分查找了

完整代码

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        """
        dp(k, n) n层k个鸡蛋最少需要移动多少次

        """
        dp = [[0]*(n+1) for _ in range(k+1)]
        dp[1][:] = range(0, n+1)

        for i in range(2, k+1):
            for j in range(1, n+1):
                res = float("INF")
                # for c in range(1, j+1):
                #     res = min(res, max(dp[i][j-c], dp[i-1][c-1])+1) kNN复杂度
                l, r = 1, j
                while(l <= r):
                    m = (l+r) // 2

                    if dp[i][j-m] > dp[i-1][m-1]:
                        l = m + 1
                        res = min(res, dp[i][j-m]) + 1
                    elif dp[i][j-m] < dp[i-1][m-1]:
                        r = m - 1
                        res = min(res, dp[i-1][m-1]) + 1
                    else:
                        res = dp[i-1][m-1] + 1
                        break
                    # res = min(res, max(dp[i][j-m], dp[i-1][m-1])+1)
                dp[i][j] = res
        return dp[k][n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

逆向思维的DP（ksqrt(n)复杂度） WIN!

原题目求的是k个鸡蛋N层最少需要操作多少次才可以确定f。
转换一下： 求k个鸡蛋最多移动f次,求N的最大值

• 表示： dp[i][j]: 表示i个鸡蛋，最多移动j次的最大值N

• 初始状态：

• 状态转移：

• dp[k][f]:如果有k个蛋，可以操作f次，所能确定的楼层
  dp[k][f-1]:操作一次后还剩f-1次，蛋碎或者没碎。碎了还有k-1个蛋，没碎还有k个蛋就变成dp[k-1][f-1]
  dp[k][f] = dp[k][f-1] + dp[k-1][f-1] +1
  1:是在某一层掷出，其实我没太懂加1的具体，有点抽象

代码

dp = [[0 for _ in range(n+1)] for _ in range(k+1)]
f = 0
while dp[k][f] < n:
   f += 1
   for i in range(1, k+1):
       dp[i][f] = dp[i][f-1] + dp[i-1][f-1] + 1
return f
1
2
3
4
5
6
7

空间优化（滚动数组）

dp[i][f] = dp[i][f-1] + dp[i-1][f-1] + 1
第f列只用到了f-1列的数据，所以可以用一维数组

代码

dp = [0 for i in range(k+1)]
f = 0
while dp[k] < n:
    for i in range(k, 0, -1):
        dp[i] = dp[i] + dp[i-1] + 1
    f += 1
return f
1
2
3
4
5
6
7

至于为什么从后向前遍历：简单解释下

• 首先明确一点：从dp[k][f],变成dp[k]
• 每一次for i in range(k, 0, -1): dp[i] = dp[i] + dp[i-1] + 1
  在dp[i] + dp[i-1] + 1还没赋值给dp[i]时，dp[i]保存的时上一轮f,i的值，也就是说
  在dp[i] + dp[i-1] + 1还没赋值给dp[i]时， dp[i]=dp[i][f-1]
  但一旦将dp[i] + dp[i-1] + 1赋值给dp[i]时， dp[i]=dp[i][f], 代表这一轮f的值，上一轮f-1的状态就被覆盖掉了，这也是为什么从后往前遍历的原因

对比一下

dp[i][f] = dp[i][f-1] + dp[i-1][f-1] + 1
dp[i] = dp[i] + dp[i-1] + 1
1
2

如果从前向后 ，当i变成i+1时

dp[i+1][f] = dp[i+1][f-1] + dp[i][f-1] + 1

dp[i+1] = dp[i+1] + dp[i] + 1
"""
从前往后问题出在这儿的
dp[i]应该对应二维dp[i][f-1]的值

现在的dp[i]是已经更新的 dp[i] = dp[i] + dp[i-1] + 1
				      dp[i][f] = dp[i][f-1] + dp[i-1][f-1] + 1 不在单纯是dp[i][f-1]的值了，被覆盖了
"""
"""
我们看看从后向前,i变成i-1
dp[i-2]的值应该对应二维dp[i-2][f-1]
而由于从后向前遍历，dp[i-2]的值并没有变化过，所以这里还是对应的二维数组中dp[i-2][f-1]
"""
dp[i-1][f] = dp[i-1][f-1] + dp[i-2][f-1] + 1

dp[i-1] = dp[i-1] + dp[i-2] + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19