当前位置:   article > 正文

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

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

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

![在这里插入图片描述](https://img-blog.csdnimg.cn/224ab9e1f669459cb27cce9a608e85a4.png

  • 首先明确一点:从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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/723576
推荐阅读
相关标签
  

闽ICP备14008679号