• 算法通关村第十九关:白银挑战-动态规划高频问题


    白银挑战-动态规划高频问题

    1. 最少硬币数

    LeetCode 322
    https://leetcode.cn/problems/coin-change/description/

    思路分析

    尝试用回溯来实现
    假如coins=[2,5,7],amount=27,求解过程中,每个位置都可以从[2,5,7]中选择,因此可以逐步将所有情况枚举出来,然后再找到要求的最少硬币数,图示如下:
    在这里插入图片描述

    通过上面的图,发现 f[20] 等已经存在多次重复计算了,存在大量重复计算的问题,效率低。

    尝试用贪心来实现
    直觉告诉我们尽量使用大的,假如coins=[2,5,7],amount=27
    先连续用 7+7+7=21,剩下6用2+2+2=6,一共 7+7+7+2+2+2=27,共使用了6枚硬币
    但我们可以使用 7+5+5+5+5=27,使用5枚硬币就够了
    贪心的思路不能解决本题

    尝试用DP来实现
    使用DP能同时满足效率和准确性

    设状态f(x),最少用f(x)枚硬币能拼出x
    建立数组arr,索引表示的是 amount,表示最少需要arr[i]个硬币能拼出来
    其中有些位放的是M,表示就是不能拼出来的意思

    coins = [1,2,5] 时
    在这里插入图片描述

    coins = [2,5,7] 时
    在这里插入图片描述

    以coins=[2,5,7],详细分析一步步实现DP

    第一步:确定状态和子问题

    状态
    f(x),最少用f(x)枚硬币能拼出x

    子问题
    先看最后一步,从后向前找递归

    • 最优策略K枚硬币,a1, a2, … ak 面值加起来是27
    • 除掉最后一枚硬币ak,前面硬币加起来面值就是 27-ak
    • ak一定是 2,5,7 中的一枚
      • 如果ak=2,f(27)=f(25)+1
      • 如果ak=5,f(27)=f(22)+1
      • 如果ak=7,f(27)=f(20)+1
    • f(27)=min(f(25),f(22),f(20))+1

    在这里插入图片描述

    f(27)=min(f(25),f(22),f(20))+1
    接下来,根据递归的思想再去算 f(25),f(22),f(20)…

    其中f(6)=min(f(4),f(1),f(-1))+1
    f(1)和f(-1)不满足要求,需要设置为正无穷
    f(4)=2,f(6)=2+1=3

    总结:递推要从右向左,计算要从左向右

    第二步:确定状态转移方程

    子问题确定之后,状态转移方程也基本确定了
    在这里插入图片描述

    f(x) = min(f(x-2), f(x-5), f(x-7)) + 1

    第三步:确定初始条件和边界

    初始条件 f(0) = 0
    如果不能拼出x,就定义f(x)为正无穷

    注意溢出问题:
    如果不能拼定义为正无穷,可能存在溢出问题
    可以用amount来代替正无穷

    第四步:按顺序计算

    执行状态转移方程 f(x) = min(f(x-2), f(x-5), f(x-7)) + 1 对数组进行计算
    递推要从右向左,计算要从左向右

    第五步:代码实现

    第一版代码

    # 伪代码
    def coin(coins, amount):
        max_num = amount + 1
        dp = [max_num] * (amount + 1)
        dp[0] = 0
        for i in range(amount + 1):
            if check(i):
                dp[i] = min(dp[i - coins[0]], dp[i - coins[1]], dp[i - coins[2]]) + 1
        return dp[amount] if dp[amount] < max_num else -1
    
    
    def check(i, coins):
        # 这里要保证 i - coins[i] 大于0
        # 这里还要保证不越界,写起来比较复杂,我们理解功能即可
        pass
        
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    第二版代码

    # 伪代码
    def coin(coins, amount):
        max_num = amount + 1
        dp = [max_num] * (amount + 1)
        dp[0] = 0
        for i in range(amount + 1):
            if check(i):
                dp[i] = min(dp[i], dp[i - coins[0]] + 1)
                dp[i] = min(dp[i], dp[i - coins[1]] + 1)
                dp[i] = min(dp[i], dp[i - coins[2]] + 1)
        return dp[amount] if dp[amount] < max_num else -1
    
    
    def check(i, coins):
        # 这里要保证 i - coins[i] 大于0
        # 这里还要保证不越界,写起来比较复杂,我们理解功能即可
        pass
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    如果 coins[] 数组比较大,if判断就非常长,考虑价格循环解决,最终代码实现如下

    第三版代码

    class Solution:
        def coinChange(self, coins: List[int], amount: int) -> int:
            max_num = amount + 1
            dp = [max_num] * (amount + 1)
            dp[0] = 0
            for i in range(1, amount + 1):
                for j in range(len(coins)):
                    if i - coins[j] >= 0:
                        dp[i] = min(dp[i], dp[i - coins[j]] + 1)
            return dp[amount] if dp[amount] < max_num else -1
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    总结一下求最值型DP的步骤

    1. 确定状态和子问题。
      从最后一步开始(最优策略中使用的最后一枚硬币ak)推导f(n)与子问题之间的关系,然后将其化成子问题(最少的硬币拼出更小的面值27-ak)

    2. 通过状态,可以得到状态转移方程 f(x) = min(f(x-2), f(x-5), f(x-7)) + 1

    3. 处理初始条件和边界问题。f[0]=0,其他如果不能拼出来标记为 f(x)=正无穷

    4. 从小到大开始计算。这里就是从 f(0),f(1),f(2)…向后计算

    2. 最长连续递增子序列

    LeetCode 674
    https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/

    思路分析

    不用动态规划也能解决,例如前面介绍的滑动窗口就可以

    动态规划解决

    在这里插入图片描述

    第一步:分析状态和子问题
    状态 f(i) ,以a[i]结尾的最长连续上升子序列的长度

    最后一个元素a[j],存在两种情况

    1. a[j]<=a[j-1],f[j]=1 (a[j]<=a[j-1] or j=0)
    2. a[j]>a[j-1],f[j] = f[j-1]+1 (j>0且a[j]>a[j-1])

    第二步:转移方程
    f[j]=1 a[j]<=a[j-1] or j=0)
    f[j] = f[j-1]+1 j>0且a[j]>a[j-1]

    第三步:初始条件和边界
    f[j]=1 a[j]<=a[j-1] or j=0)
    f[j] = f[j-1]+1 j>0且a[j]>a[j-1]

    第四步:按照顺序计算
    和硬币组合不一样,答案为 max([f(0), f(1), f(2), … ,f(n-1)])

    代码实现

    class Solution:
        def findLengthOfLCIS(self, nums: List[int]) -> int:
            # 动态规划
            arr = [1] * len(nums)
            for i in range(1, len(nums)):
                if nums[i] > nums[i-1]:
                    arr[i] = arr[i-1] + 1
            return max(arr)
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    3. 最长递增子序列

    LeetCode 300
    https://leetcode.cn/problems/longest-increasing-subsequence/description/、

    思路分析

    本题与上一题 LeetCode 674 的区别:没有说子序列元素一定是连续的

    在这里插入图片描述

    使用DP解决问题的方法

    第一步:确定状态和子问题
    状态f(x) 第x个元素的最长递增子序列长度,求以a[x]结尾的最长上升子序列

    子问题:
    情况1:最长上升子序列为 { a[j] },f[j] = 1
    情况2:最长上升子序列大于1
    0<=ia[i],f[j] = f[i]+1
    在这里插入图片描述

    因为不确定最优策略中a[j]前一个元素a[i]是哪一个,需要枚举每个i,求以a[j]结尾的最长上升子序列
    在这里插入图片描述

    第二步:初始条件和边界
    f[0] = 1
    情况2必须满足
    1.0<=i 2. a[j]>a[i]

    第三步:计算顺序
    计算 f[0],f[1],…,f[n-1]
    答案就是这些数中最大的那个

    代码实现

    class Solution:
        def lengthOfLIS(self, nums: List[int]) -> int:
            # 动态规划
            arr = [1] * len(nums)
            for i in range(1, len(nums)):
                for j in range(i):
                    if nums[i] > nums[j]:
                        arr[i] = max(arr[j] + 1, arr[i])
            return max(arr)
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    class Solution:
        def lengthOfLIS(self, nums: List[int]) -> int:
            # 动态规划
            dp = []
            for i in range(len(nums)):
                dp.append(1)
                for j in range(i):
                    if nums[i] > nums[j]:
                        dp[i] = max(dp[j] + 1, dp[i])
            return max(dp)
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    4. 最少完全平方数

    LeetCode279
    https://leetcode.cn/problems/perfect-squares/description/

    思路分析

    手动画一下
    在这里插入图片描述

    使用DP来实现

    第一步:确定状态和子问题
    状态:f[i] i最少被分成几个完全平方数之和
    子问题:参考硬币的问题,f[i] = min(f[i-j*j]+1, f[i]) 1<=j

    第二步:状态转移方程
    f[i] = min(f[i-j*j]+1, f[i]) 1<=j

    第三步:初始和边界条件
    f[0] = 0

    第四步:计算顺序
    计算 f[0],f[1],…,f[n-1],f[n]
    答案就是f[n]

    代码实现


    class Solution:
        def numSquares(self, n: int) -> int:
            dp = [0]
            for i in range(1, n + 1):
                dp.append(i)
                for j in range(1, int(i**0.5) +1):
                    dp[i] = (min(dp[i-j**2]+1, dp[i] ))
            return dp[n]
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    5. 再论青蛙跳

    LeetCode 55
    https://leetcode.cn/problems/jump-game/description/

    思路分析
    典型的贪心问题,下面从动态规划的角度来分析解题

    1. 状态和子问题
      状态:f[x] 能否跳跃值x
      子问题:可以跳到j,j可以跳到i
    2. 状态转移方程
      f[i] = True | 0<=j=i-j
    3. 初始和边界条件
      f[0] = True
    4. 顺序
      计算 f[0],f[1],…,f[n-1] 答案就是f[n-1]

    代码实现

    class Solution:
        def canJump(self, nums: List[int]) -> bool:
            # 动态规划
            bp = [False] * len(nums)
            bp[0] = True
            for i in range(1, len(nums)):
                for j in range(i):
                    if bp[j] and nums[j] >= i - j:
                        bp[i] = True
            return bp[-1]
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    注:动态规划可以实现,但在LeetCode上,运行超出时间限制

    6. 解码问题

    LeetCode 91
    https://leetcode.cn/problems/decode-ways/description/

    思路分析

    1. 状态和子问题
      状态:f[i] 以a[i]结尾,可以有多少种解码方式
      子问题:
      最后一个字母的解码有两种情况
      情况1:1个数字解码 a[i]对应一个字母,f[i] = f[i-1]
      情况2:2个数字解码 a[i-1]a[i]对应一个字母,f[i] = f[i-2]

      综上,f[i] = f[i-1](条件:a[i]可以对应一个字母) + f[i-2](条件:a[i-1]a[i]可以对应一个字母)

    2. 状态转移方程
      f[i] = f[i-1](条件:a[i]可以对应一个字母) + f[i-2](条件:a[i-1]a[i]可以对应一个字母)

    3. 初始和边界条件
      初始条件f[0] = 1 理解为空串,有一种解码方式
      边界条件:i = 1,只看最后一个数字就行了

    4. 顺序
      计算 f[0],f[1],…,f[n-1] 答案就是f[n]

    代码实现

    class Solution:
        def numDecodings(self, s: str) -> int:
            n = len(s)
            dp = [0] * (n + 1)
            dp[0] = 1
            for i in range(1, n + 1):
                if s[i - 1] != '0':
                    dp[i] += dp[i - 1]
                if i > 1 and 10 <= int(s[i - 2]) * 10 + int(s[i - 1]) <= 26:
                    dp[i] += dp[i - 2]
            return dp[len(s)]
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    7. 路径中存在障碍物

    LeetCode 63
    https://leetcode.cn/problems/unique-paths-ii/description/

    我们在路径部分介绍了多种路径的问题
    本专题有个重要的拓展,加入网格中存在障碍物怎么办?

    本题是在 LeetCode 62 的基础上,如果中间某个位置存在障碍物,那一共有多少种路径。

    示例
    输入    obstacleGrid = [[0,0,0], [0,1,0], [0,0,0]]
    输出    2
    解释    3x3 网格的正中间有一个障碍物
            从左上角到右下角一共有2条不同的路径
            1. 向右->向右->向下->向下
            2. 向下->向下->向右->向右
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    在这里插入图片描述

    思路分析

    处理方法不算复杂
    设置没有障碍物的格子标记为0,有障碍物的格子标记为1
    执行的时候如果当前位置dp[i][j] == 1时,直接跳过

    代码实现

    class Solution:
        def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
            m = len(obstacleGrid)
            n = len(obstacleGrid[0])
            bp = [[0] * n for _ in range(m)]
            bp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
            for i in range(m):
                for j in range(n):
                    if obstacleGrid[i][j] == 1:
                        bp[i][j] = 0
                    elif i >= 1 and j >= 1:
                        bp[i][j] = bp[i - 1][j] + bp[i][j - 1]
                    elif i >= 1:
                        bp[i][j] = bp[i - 1][j]
                    elif j >= 1:
                        bp[i][j] = bp[i][j - 1]
            return bp[-1][-1]
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    class Solution:
        def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
            # 滚动数组实现
            m = len(obstacleGrid)
            n = len(obstacleGrid[0])
            dp = [0] * n
            dp[0] = 1 if obstacleGrid[0][0] == 0 else 0
            for i in range(m):
                for j in range(n):
                    if obstacleGrid[i][j] == 1:
                        dp[j] = 0
                    elif j - 1 >= 0 and obstacleGrid[i][j - 1] == 0:
                        dp[j] += dp[j - 1]
            return dp[n - 1]
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    8. 滚动数组技巧

    LeetCode 118
    https://leetcode.cn/problems/pascals-triangle/description/
    LeetCode 119
    https://leetcode.cn/problems/pascals-triangle-ii/description/

    杨辉三角
    特点:每个元素嗾使其二维矩阵中左上方和右上方的元素之和,是一种对称结构
    在这里插入图片描述

    用二维数组表示
    在这里插入图片描述

    • 每一行的最右侧和最左侧都是1
    • 前两行时1,第3行才开始有累加的问题
    • 每一行的元素数量与其行数一样

    代码实现

    LeetCode 119

    class Solution:
        def getRow(self, rowIndex: int) -> List[int]:
            # 新建二维数组
            a = [[] for _ in range(rowIndex+1)]
    
            for i in range(rowIndex+1):
                # 确定每一行数组
                a[i] = [0] * (i + 1)
                # 第1个和最后1个元素为1
                a[i][0] = 1
                a[i][i] = 1
    
            for i in range(rowIndex+1):
                # 从第3行开始
                if i >= 2:
                    for j in range(1, len(a[i]) - 1):
                        a[i][j] = a[i - 1][j - 1] + a[i - 1][j]
    
            return a[-1]
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    思路分析

    如果要求只能使用O(n)空间实现呢?可以使用上面提到的滚动数组来做

    a[i][j] = a[i-1][j-1] + a[i-1][j]

    存在问题:计算dp[i]的时候,需要上一轮的dp[i-1],但是这个值已经被覆盖了
    例如下图中的 3 需要使用上一轮的2和1进行相加,但是此时2已经覆盖成3了,所以仅靠一个一维数组无法解决问题

    在这里插入图片描述

    可以使用两个数组,也是O(n)空间,使用两个数组来进行轮换交流
    如下图所示,黑色代表上一轮的结构,红色表示当前轮更新的结果
    在这里插入图片描述

    代码实现

    LeetCode 119

    class Solution:
        def getRow(self, rowIndex: int) -> List[int]:
            # 滚动数组,两个一维数组
            pre = []
            cur = []
            for i in range(rowIndex+1):
                for j in range(i + 1):
                    if j == 0 or i == j:
                        cur.append(1)
                    else:
                        cur.append(pre[j - 1] + pre[j])
                pre = cur
                cur = []
            return pre
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    思路分析

    如果只能使用一个一维数组来完成,该怎么做呢?

    观察 cur[j] = pre[j-1] + pre[j],第 j 项的计算与上一行第 j-1 项和第 j 项有关

    可以倒着算,就没有影响了,先计算第 j 项,再计算第 j-1 项,这样计算第 j 项时,第 j-1 项还是上一行的值
    cur[j] = cur[j-1] + cur[j]

    # 两个二维数组
    for j in range(i + 1):
        if j == 0 or i == j:
            cur.append(1)
        else:
            cur.append(pre[j - 1] + pre[j])
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    变为

    # 一个二维数组
    for j in range(i, -1, -1):
        if j == 0 or i == j:
            arr[j] = 1
        else:
            arr[j] = arr[j - 1] + arr[j]
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    代码实现

    LeetCode 119

    class Solution:
        def getRow(self, rowIndex: int) -> List[int]:
            # 滚动数组,一个一维数组
            arr = []
            for i in range(rowIndex+1):
                arr.append(0)
                for j in range(i, -1, -1):
                    if j == 0 or i == j:
                        arr[j] = 1
                    else:
                        arr[j] = arr[j - 1] + arr[j]
            return arr
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
  • 相关阅读:
    Cocos Creator开发学习路线
    TKE 超级节点,Serverless 落地的最佳形态
    【PyCharm Community Edition】:基础
    python opencv识别蓝牌车牌号 之 取出车牌号 (1/3)
    Redis之Redis基础、环境搭建、主从切换
    Debian安装PostgreSQL16及其plpython3u扩展
    Html5+Css3第一讲:html5+Css3基础(2)
    06- 诊断事件DemEventParameter的配置
    使用脚本启动和关闭微服务
    C/C++数据结构——最优屏障(栈)
  • 原文地址:https://blog.csdn.net/qq_41662142/article/details/132854213