算法笔记-动规总结

前言

陆陆续续刷了许多carl老师博客上的动规题目，即便是现在我仍然还是有一点点晕，所以想对我刷的题型做一个总结来理清自己的思路

一、动规基础介绍与解题步骤：

动态规划（Dynamic Programming，DP）的方法求解，动态规划的三要素：最优子结构、边界和状态转移函数。

边界 问题最小子子集的解（初始范围）
最优子结构 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到
状态转移函数 从一个阶段向另一个阶段过度的具体形式,描述的是两个相邻子问题之间的关系(递推式)

在解题的时候有动规五部曲：

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

而不同的题型难点也不同，有点初始化dp难有的遍历顺序难，还有的递推公式难。

二、基础题型：

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

对于这个题，只要理解了dp的递推公式就很容易，当然它本身也很简单。

因为一次可以走1 or 2步，所以假如要走到第9阶那么就可以从第7或者8阶走。 所以很明显走到第九阶的方法=走到第八阶+走到第七阶。即：

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

所以咱们的dp数组的初始化就必须得自己初始化前面两阶，后面的数据可以无所谓，因为反正也会被覆盖掉。
所以本体解题步骤就为

class Solution:
    def climbStairs(self, n: int) -> int:
        dp=[0]*10086
        dp[1]=1
        dp[2]=2
        if n<=3:
            return n
        for i in range(3,n+1):
            dp[i]=dp[i-1]+dp[i-2]
        return dp[n]

爬楼梯Ⅱ：

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i
个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。

• 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。

此题跟前一步爬楼梯问的点不同，所以差别就在于dp的递归函数。因为依旧是只能走1或2阶所以依旧是初始化前两步。

dp[i]=min(dp[i-1],dp[i-2])+cost[i]

显而易见就是说选取前面两个中花费最小的到达该台阶
所以可以这样解答：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp=[0]*len(cost)
        dp[0]=cost[0]
        dp[1]=cost[1]
        for i in range(2,len(cost)):
            dp[i]=min(dp[i-1],dp[i-2])+cost[i]
        return min(dp[len(cost)-1],dp[len(cost)-2])

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

这个题在我看来跟爬楼梯是一摸一样的，只不过它从一维变成了二维。
它也是一样，一个位置可以从左边或者上边过来，所以

来到一个位置的组合就等于到上面的组合+到左边的组合

所以dp函数就为

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

但是有一点是不同的，它的初始化应该把第一排与第一列都初始化，因为dp函数就已经摆明了不能去搞边缘的地方，只能从[1][1]开始
所以

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp=[[1 for i in range(n)] for j in range(m)]
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
        return dp[-1][-1]

路径组合Ⅱ

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

这个题就因为多了一个障碍物的可能，把题瞬间就整难了不少啊

由于多了障碍物，初始化也变复杂了，之前只需都搞成一就行了。现在如果在边缘有障碍物的话那么障碍物后面就一定只能是0了。所以初始化应该这样

# 第一行
        for i in range(1, col):
            if obstacleGrid[0][i] != 1:
                dp[0][i] = dp[0][i-1]

        # 第一列
        for i in range(1, row):
            if obstacleGrid[i][0] != 1:
                dp[i][0] = dp[i-1][0]

并且还要判断起始点，如果一来就是个障碍物那还走啥，走个寂寞
在dp函数上只需判断是否为障碍点就行了。

还有就是初始化其他点也必须初始为0，因为遇到障碍就不处理，就默认为0了。
所以可以这样写：

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        row = len(obstacleGrid)
        col = len(obstacleGrid[0])
        dp = [[0 for _ in range(col)] for _ in range(row)]

        dp[0][0] = 1 if obstacleGrid[0][0] != 1 else 0
        if dp[0][0] == 0: return 0  # 如果第一个格子就是障碍，return 0
        # 第一行
        for i in range(1, col):
            if obstacleGrid[0][i] != 1:
                dp[0][i] = dp[0][i-1]

        # 第一列
        for i in range(1, row):
            if obstacleGrid[i][0] != 1:
                dp[i][0] = dp[i-1][0]
        print(dp)

        for i in range(1, row):
            for j in range(1, col):
                if obstacleGrid[i][j] != 1:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

整数拆分：

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。

对于这个题其实难点还是dp的递归函数，这类简单的体型初始化与遍历顺序都不会有太大的问题。
这是dp函数

dp[i]=max(dp[i],max((i-j)*j,dp[i-j]*j))

j代表的是拆分的整数，所以它的范围应该是

for j in range(1,i-1):

本身和0肯定是不能取的

这个递归函数中有三种可能，在这三种中取max就是局部最优解

1.不拆分
2.拆分成i-j与j
3.拆分成i与dp[i-j],dp[i-j]就是对i-j那个数在dp中最大的状态

所以该题可以这样解：

class Solution:
    def integerBreak(self, n: int) -> int:
        dp=[0]*(n+1)
        dp[2]=1
        for i in range(3,n+1):
            for j in range(1,i-1):
                dp[i]=max(dp[i],max((i-j)*j,dp[i-j]*j))
        return dp[n]

因为1和0拆分是没有意义的所以不用管

三、01背包系列

介绍：

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i]
每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

对于这种题我认为难点就是把题转换成经典的背包问题

背包问题理解了本身并不难

二维的dp[i][j]代表从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

所以就有两个状态，放或者不放:

不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i -
1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)

放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为 j -
weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i]
（物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] +
value[i]);

对于初始化就只需要初始化背包容量为0时最大价值都是0
由于递归公式需要上一个状态，所以第一个物品的那一排也是需要初始化的

    for j in range(1, cols):     
        if first_item_weight <= j: 
            dp[0][j] = first_item_value

演变题型：

分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11]

这题想要把他转变成背包类的题就是要找到代替背包容量的值
物品显然就是nums里的值了，读题要找到等和，那我们只需找到能
组成sum（nums）一半的子集不就行了吗，所以背包容量就是总和的一半
还有如果sun为奇数则不可能有解
则：

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        taraget = sum(nums)
        if taraget % 2 == 1: 
            return False
        taraget //= 2
        dp = [[0 for _ in range(taraget+1)] for _ in range(len(nums))]
        for i in range(0,taraget+1):
            if i>=nums[0]:
                dp[0][i]=nums[0]
        for i in range(1,len(nums)):
            for j in range(1,taraget+1):
                if j>=nums[i]:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j - nums[i]] + nums[i])
                else:
                    dp[i][j]=dp[i-1][j]
        return taraget == dp[len(nums)-1][taraget]

最后一块石头的重量：

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为
y-x。 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

这一题跟分割等和子集的转变成背包问题的思想非常类似，target=sum（stones）/2就是咱们的背包容量，这个最大容量能装的最大重量就是一堆石头的最大重量了，另外一堆就是sum-target，所以剩下的石头重量显然是sum-2target。由于/是向下取整，sum就不存在小于2dp[target]的情况了

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        target=sum(stones)
        target//=2
        dp=[0 for _ in range(target+1)]
        for i in range(len(stones)):
            for j in range(target,0,-1):
                if j<stones[i]:
                    dp[j]=dp[j]
                else:
                    dp[j]=max(dp[j],dp[j-stones[i]]+stones[i])

        return sum(stones)-dp[-1]*2

目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

这个题我是真的认为将它转换成背包问题是一个很难的地方，背包容量究竟该怎样找很不容易

假设加法的总和为x，那么减法对应的总和就是sum - x。

所以我们要求的是 x - (sum - x) = S

x = (S + sum) / 2

确立递归公式比较容易，就是在
例如：dp[j]，j 为5，

已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 dp[5]。
已经有一个2（nums[i]） 的话，有 dp[3]种方法凑成 dp[5]。
已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 dp[5]
已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 dp[5]
已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 dp[5]
那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

所以求组合类问题的公式，都是类似这种：

dp[j] += dp[j - nums[i]]

所以理解不到也可以死记硬背。

所以最终答案应该是

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        sumValue = sum(nums)
        #注意边界条件为 target>sumValue or target<-sumValue or  (sumValue + target) % 2 == 1
        if abs(target) > sumValue or (sumValue + target) % 2 == 1: return 0
        bagSize = (sumValue + target) // 2
        dp = [0] * (bagSize + 1)
        dp[0] = 1
        for i in range(len(nums)):
            for j in range(bagSize, nums[i] - 1, -1):
                dp[j] += dp[j - nums[i]]
        return dp[bagSize]

一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4 解释：最多有
5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括
{"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3

该题也是01背包的衍生问题，不过背包却有两个维度。

确定dp数组（dp table）以及下标的含义
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

然后我们在遍历的过程中，取dp[i][j]的最大值。

所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

而初始化跟遍历顺序都与01背包一样

所以

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]    # 默认初始化0
        # 遍历物品
        for str in strs:
            ones = str.count('1')
            zeros = str.count('0')
            # 遍历背包容量且从后向前遍历！
            for i in range(m, zeros - 1, -1):
                for j in range(n, ones - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)

        return dp[m][n]

四、完全背包系列

题型介绍：

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]
。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

而在01背包讲过将二维压缩成一维提过的在遍历背包容量的时候，要倒序遍历，不然会重复装物品，所以完全背包就正好相反，就是去正序遍历重复装物品。

衍生题型：

零钱兑换Ⅱ：

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

这个题就是典型的完全背包了

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0]*(amount + 1)
        dp[0] = 1
        # 遍历物品
        for i in range(len(coins)):
            # 遍历背包
            for j in range(coins[i], amount + 1):
                dp[j] += dp[j - coins[i]]
        return dp[amount]

而这个组合数跟前面题的动规函数是一样的。都是相同的

还有一个进阶的零钱兑换，就是得出兑换钱币数量最少的情况

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp=[amount+1 for _ in range(amount+1)]

        dp[0]=0
        for i in range(len(coins)):
            for j in range(coins[i],amount+1):
                dp[j]=min(dp[j],dp[j-coins[i]]+1)

        return dp[amount] if dp[amount] < amount + 1 else -1

这里这个dp[j]=min(dp[j],dp[j-coins[i]]+1)‘+1’是要加上coins[i]这张纸币的数量

五、 打家劫舍系列

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

这个题就给动规的递归函数多了一个限制，不能连续偷
所以就应该

 dp [i]=max(dp[i-1],dp[i-2]+nums[i])

决定dp[i]的因素就是第i房间偷还是不偷。

如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出
下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，

然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

而对于dp数组的初始化因为dp数组当前状态需要看前两家的状态，所以必须初始前两家的偷家状态

dp[0]=nums[0]
dp[1]=max(nums[0],nums[1])

所以该题就出来了

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        dp=[0 for _ in range(len(nums))]
        dp[0]=nums[0]
        dp[1]=max(nums[0],nums[1])
        for i in range(2,len(nums)):
            dp [i]=max(dp[i-1],dp[i-2]+nums[i])
        return max(dp)

打家劫舍Ⅱ

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈
，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）,
因为他们是相邻的。

这个题比起上一题就多了一个限制，就是头尾的问题，因为是一个环，所以头尾也是相连的了，所以就有两种情况，选择偷头还是偷尾
也就是说两次动规数组分别是要头和要尾然后取最大值

class Solution:
    def rob(self, nums: List[int]) -> int:
        #在198入门级的打家劫舍问题上分两种情况考虑
        #一是不偷第一间房，二是不偷最后一间房
        if len(nums)==1:#题目中提示nums.length>=1,所以不需要考虑len(nums)==0的情况
            return nums[0]
        val1=self.roblist(nums[1:])#不偷第一间房
        val2=self.roblist(nums[:-1])#不偷最后一间房
        return max(val1,val2)

    def robRange(self,nums):
        l=len(nums)
        dp=[0]*l
        dp[0]=nums[0]
        for i in range(1,l):
            if i==1:
                dp[i]=max(dp[i-1],nums[i])
            else:
                dp[i]=max(dp[i-1],dp[i-2]+nums[i])
        return dp[-1]