【LeetCode】动态规划类题目详解

所有题目均来自于LeetCode，刷题代码使用的Python3版本

动态规划

问题分类

如果某一个问题有重叠的子问题，则使用动态规划进行求解是最有效的。

动态规划中每一个状态一定是由上一个状态推导出来的，这一点区别于贪心算法

动态规划五部曲

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

背包问题

• 01背包
• 完全背包

01背包 | 二维数组进行求解

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

递归五部曲

• 确定dp数组含义

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

• 确定递推公式

  • 有两种情况：
    • 不放物品
      • dp[i][j] = dp[i-1][j] 即当前dp数组的上一个的位置。这个含义就是，容量为j但是不放入i物品，只选择前i-1个物品
    • 放物品
      • dp[i][j] = dp[i-1][j-weight[i]] + value[i]。位于当前位置的左上方，不一定正好是左上角，有可能是左上角的前面的位置。这里的含义就是需要将当前位置的重量减去，然后再加上当前位置的物品价值。注意这里是**dp[i-1][j-weight[i]]**而不是dp[i][j-weight[i]]
      • 当前的最大总价值应该取二者中的最大值，即dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

并且需要注意，如果j<weight[i]的时候，是不能放物品的，因为这样的情况是无法作为数组的下标的。

放物品时候的理解：当i放进去的时候，背包的总重量为j，前i-1个能放的物品剩余重量就只剩下j-weight[i]，前i-1个物品中能够获得的最大价值为dp[i-1][j-weight[i]]，再加上当前物品i放进去的价值value[i]。这是当前放物品能够获得的最大价值。

• 初始化

dp = [[0]*(n+1) for i in range(m)]

当j=0的时候，表示当前背包能够载重为0，此时不管选择几号物品，dp[i][j]都等于0

当i=0的时候，表示当前只取物品0，此时只有在j>=weight[0]的时候，dp[0][j]=value[0]

for j in range(weight[0], n+1):
    dp[0][j] = value[0]

• 遍历顺序

先遍历物品或者先遍历背包都是可以的，为了和滚动数组一致，先遍历物品（几号物品）再遍历背包（背包的重量/容量）

# m代表材料的数量，n代表背包载重
m, n = map(int, input().split())

# M 代表研究材料的种类 N代表行李空间
weight = list(map(int, input().split()))  # 代表重量
value = list(map(int, input().split()))  # 代表价值

# 全部初始化为0
dp = [[0] * (n + 1) for _ in range(m)]

# 初始化dp数组第一列  下面这部分代码可以不写 ，因为在初始化的时候就全部初始化为0了
# for i in range(m):
#     dp[i][0] = 0
# 初始化dp数组第一行
for i in range(weight[0], n + 1):
    dp[0][i] = value[0]

for i in range(1, m):  # 先遍历物品
    for j in range(1, n + 1):  # 再遍历背包
        if j < weight[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

# print(weight)
# print(value)
# for i in dp:
#     print(i)
print(dp[m - 1][n])

滚动数组 | 01背包 二维降到一维

• dp数组含义

dp[j]表示当容量为j的时候背包所背的物品最大价值

• 递推公式

跟使用二维数组的时候一样，通过两种方式获得dp[j]：

放物品i

​ 当放物品i的时候，dp[j] = dp[j-weight[i]] + value[i]

不放物品i

​ 当不放物品i的时候dp[j] = dp[j-1]

递推公式为

dp[j] = max(dp[j], dp[j-weight[i]]+value[i])

• 初始化

dp[j]表示背包容量为j的时候所背物品的最大价值，则dp[0]表示物品容量为0，结果必然为0

其余的下标都是通过递推的方式从dp[0]推出，因此全部初始化为0即可

• 遍历顺序

• 为什么需要先遍历物品在遍历重量？

如果遍历背包容量放在外层，则每个dp[j]只会放一个物品，即背包里只放了一个物品。

针对一维dp数组，背包容量需要倒序进行遍历，如果遍历背包放在上一层，那么每个dp[j]只会放入一个物品，即背包里只装一个物品

• 为什么在遍历重量的时候需要倒序遍历？（即背包重量从大到小进行遍历）

假设现在背包的情况是这样的

遍历部分的代码如下：

for i in range(m):  # 先遍历物品
    for j in range(n, weight[i] - 1, -1):  # 再遍历背包
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

dp数组初始化为全0，如果我们从后开始进行遍历的话，当遍历物品0时，weight[0] = 1，value[0] = 15

dp[1] = max(dp[1], dp[1-weight[0]] + value[0]) = max(0, 15) = 15

dp[2] = max(dp[2], dp[2-weight[0]] + value[0]) = max(0, 15+15) = 30

此时重复往背包中放入物品0了

如果我们从后往前进行遍历的话，情况如下：

dp[4] = max(dp[4], dp[4-weight[0]] + value[0]) = max(0, 15) = 15

dp[3] = max(dp[3], dp[3-weight[0]] + value[0]) = max(0, 15) = 15

dp[2] = max(dp[2], dp[2-weight[0]] + value[0]) = max(0, 15) = 15

dp[1] = max(dp[1], dp[1-weight[0]] + value[0]) = max(0, 15) = 15

这样循环往复就可以得到最终的dp数组，而dp[n]也就是最终结果

倒序进行遍历是因为每个背包只能放进去一次，正序遍历的时候会重复使用符合条件的背包价值。

遍历的代码部分中，倒序遍历的时候开始和结束的下标分别为n和weight[i]-1，n很好理解，就是dp数组中的元素个数，weight[i]-1表示什么含义呢？

因为题目中涉及到j-weight[i]这个操作，因此遍历到物品i的时候我们的结束下标j一定是等于weight[i]的

在Python的循环中，左闭右开，为了遍历到weight[i]这个重量，需要再减去1

例如当我们在遍历物品0的时候，即当前的i=0，此时weight[i]=1，为了能够用j模拟其能够开始推导递推公式，需要j-weight[i]>=0，因此j最小下标应该就是weight[i]，又由于range()的范围是左闭右开，所以结束下标应该是weight[i]-1，此时结束下标就是0，即0的时候不会在进行循环体部分。

倒序遍历原因本质上还是对二维数组的遍历，右下角的值依赖于左上角的值，因此需要保证左边的值仍然是上一层的，从右往左进行覆盖

题目链接

# m代表材料的数量，n代表背包载重
m, n = map(int, input().split())

# M 代表研究材料的种类 N代表行李空间
weight = list(map(int, input().split()))  # 代表重量
value = list(map(int, input().split()))  # 代表价值

# 全部初始化为0   表示背包重量从0-n 共计n+1个数字
dp = [0] * (n + 1)

for i in range(0, m):  # 先遍历物品
    for j in range(n, weight[i] - 1, -1):  # 再遍历背包
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

print(dp[n])

完全背包问题

完全背包和01背包的区别就在于物品是否可以重复选取，如果每个物品只能取一次，则是01背包问题，否则是完全背包问题。他们两个的区别就在于内层循环背包重量的时候，01背包中需要从后往前进行遍历防止每个物品被重复选择，而重复选择恰好是完全背包所需要的，因此完全背包需要从前往后进行遍历。

而对于完全背包问题而言，两个for循环的嵌套顺序是无所谓的

先遍历物品再遍历背包：

for i in range(len(value)):  # 遍历物品
    for j in range(weight[i], bagWeight + 1):  # 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

先遍历背包再遍历物品：

先遍历背包的时候，需要判断

for j in range(target+1): # 遍历背包
    for num in nums:  # 遍历物品
        if j>=num:
            dp[j] += dp[j-num]

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

爬楼梯进阶版：

n,m = map(int,input().split())
# 背包容量为n, 物品为m
dp = [0]*(n+1)
dp[0] = 1

for j in range(0,n+1):
    for i in range(1,m+1):# 遍历物品
        dp[j] += dp[j-i]
print(dp[n])

多重背包问题

多重背包的描述如下：

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

多重背包问题可以通过将物品数量大于1个的展开，这样就可以构成01背包问题，如下图所示：

# C为背包容量 N为类型
C, N = map(int, input().split())
# weight = []
# price = []
# nums = []
weight = list(map(int, input().split()))
price = list(map(int, input().split()))
nums = list(map(int, input().split()))
# 构造01背包
for i in range(len(nums)):
    if nums[i] > 1:
        for j in range(nums[i] - 1):
            weight.append(weight[i])
            price.append(price[i])

# print(weight, price)

dp = [0] * (C + 1)
for i in range(sum(nums)):
    for j in range(C, weight[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - weight[i]] + price[i])
print(dp[C])

练习题

509、斐波那契数列

[外链图片转存中…(img-Ehs794A0-1712798807479)]

递归解法（时间复杂度较高）

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            return self.fib(n - 1) + self.fib(n - 2)

动态规划解法

这里使用滚动数组的方式，定义了初始化值，然后进行递推，由于题目已经给出了递推公式，所以我们直接使用即可。

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        dp0 = 0
        dp1 = 1
        for i in range(2, n + 1):
            dpn = dp0 + dp1
            dp0 = dp1
            dp1 = dpn
        return dpn

[外链图片转存中…(img-WbOvAAgm-1712798807480)]

70、爬楼梯

1. 确定dp数组及其下标含义

   dp[i]：爬到第i层楼梯，有dp[i]种方法

2. 确定递推公式

   dp[i]可以从两个方向进行递推，有两种情况可以到达该层：

   • 从dp[i-1]跨 1 步即可到达
   • 从dp[i-2]跨 2 步即可到达

   所以dp[i]=dp[i-1]+dp[i-2]，即爬到第i层的方法是爬到第i-1层的方法总数加上爬到第i-2层的方法总数之和。

3. dp数组如何进行初始化

   题目给定了n的范围>=1，初始化的时候只需要从1开始初始化即可

   i=0时，dp[i]=0

   i=1时，dp[1]=1，表示踏上一层楼梯有一种方法，即跨一步

   i=2时，dp[2]=2，表示踏上二层台阶有两种方案，即跨两次一步或者直接跨两步

4. 确定遍历顺序

   从前往后进行遍历

5. 举例推导dp数组

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp0 = 1
        dp1 = 2
        for i in range(2, n):
            dpn = dp0 + dp1
            dp0 = dp1
            dp1 = dpn
        return dpn

本题和斐波那契数列递推公式一样。

746、使用最小花费爬楼梯

[外链图片转存中…(img-lna880Fp-1712798807484)]

1. 确定dp数组及其下标含义

   dp[i]：爬到第i层的花费

2. 确定递推公式

   dp[i]可以从两个方向进行递推

   • 从dp[i-1]跨一步即可到达 dp[i] = dp[i-1]+cost[i-1]
   • 从dp[i-2]跨两步即可到达 dp[i] = dp[i-2]+cost[i-2]

   因为需要最小的花销，所以取二者其中的最小值

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

3. dp数组如何进行初始化

   题目中说了你可以从下标为0或者下标为1的台阶开始爬楼梯，所以按照下面的进行计算

   i=0时，dp[i]=0

   i=1时，dp[i]=0

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

   注意本题在进行初始化的时候dp数组长度为len(cost)+1，因为需要跨过最顶层的台阶

4. 确定遍历顺序

   从前往后进行遍历

5. 举例推导dp数组

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

118、杨辉三角

[外链图片转存中…(img-VQ775g4c-1712798807485)]

思路：先进行初始化，将这个杨辉三角构建出来，默认的初始化都为值都设置为1。然后从第二行开始进行遍历，将去头掐尾的其余的值全部设置成上一行对应位置两项之和。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        # 初始化一个全新的杨辉三角
        res = [[1] * i for i in range(1, numRows + 1)]
        if numRows >= 3:
            for i in range(2, numRows):
                for j in range(1, len(res[i]) - 1):
                    res[i][j] = res[i - 1][j - 1] + res[i - 1][j]

        return res

62、不同路径

动态规划

从[0][0]到[m][n]共有多少条路径，其中机器人每次只能向下或者向右移动一步。

• 确定dp数组

dp[i][j]表示从0,0出发到i,j共有多少条路径

• 确定递推公式

dp[i][j]只能从其上方或者下方走过来，就可以写成累加的形式，表示可以从dp[i-1][j]这个位置走一步或者从dp[i][j-1]这个位置走一步过来

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

• dp数组初始化

dp[i][0]和dp[0][j]都为0

dp = [[0]*n for _ in range(m)]
for i in range(m):
    dp[i][0] = 1
for i in range(n):
    dp[0][i] = 1

• 确定遍历顺序

都是从上方或者左方推导过来的，从左到右一层一层进行遍历即可

• 举例推导dp数组

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # dp = [[0]*n]*m
        # 在Python中[[0]*n]*m表示使用相同的行列表示m次 这样实际所有行的引用都指向一个对象 
        # 初始化
        dp = [[0]*n for _ in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for i in range(n):
            dp[0][i] = 1
        # for i in dp:
        #     print(i)
        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[m-1][n-1]

63、不同路径II

[外链图片转存中…(img-iAjsx5Ue-1712798807488)]

本题和上一题的区别就在于地图中有障碍物影响了行走，但是本题只需要保证障碍物的位置处，dp[i][j]始终保持为0即可。

• dp数组含义

dp[i]][j]从下标为0,0的起点出发，到下标为i,j的位置，总共有多少条路径

• 递推公式

递推公式和上一题一样：dp[i][j] = dp[i-1][j] + dp[i][j-1]，区别就在于必须是在没有障碍物的位置才能够更新dp[i][j]

• dp数组初始化

本题在进行初始化的时候需要注意，在碰到障碍物之后，就没有路了，如下图所示

所以需要进行特殊处理，即当碰到有障碍物的地方就直接设置为0，需要对第一行和第一列进行这样的特殊处理，其余的位置可以不用进行处理。

• 确定遍历顺序

从左到右进行遍历

在遍历的时候，如果到了障碍物的位置，直接continue

• 举例推导dp数组

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [[0]*n for _ in range(m)]
        # print(dp)
        for i in range(m):
            if obstacleGrid[i][0]==0:
                dp[i][0] = 1
            else:
                break
        for i in range(n):
            if obstacleGrid[0][i]==0:
                dp[0][i] = 1
            else:
                break
        # for i in dp:
        #     print(i)
        for i in range(1,m):
            for j in range(1,n):
                if obstacleGrid[i][j]==0:
                    dp[i][j] = dp[i-1][j]+dp[i][j-1]
        # for i in dp:
        #     print(i)
        return dp[m-1][n-1]

343、整数拆分（*）

[外链图片转存中…(img-z9wjxz50-1712798807490)]

• dp数组表示什么含义

  • dp[i] 表示i能拆分得到的最大乘积

• dp数组递推公式

  • dp[i]可以由两个方向得到
  • j*（i-j) 这个的含义是i-j不进行拆分，直接相乘
  • j*dp[i-j] 这个的含义是i-j也进行拆分，并用拆分后的最大值与之相乘

• dp数组初始化

  • dp[0]和dp[1]没有实际意义 题目也说了n>=2
  • dp[2] = 1
  • 循环i从3开始

• 遍历遍历顺序

  • 从前往后进行遍历

• 举例

注意代码在进行拆分的时候j是从1到i//2+1范围的，python中for循环遍历的范围是前闭后开的所以要加上1，这里可以以4为例，4//2=2，取开区间只能取到1，不符合要求了。

假设正整数i拆分出来的第一个正整数为j （1<=j<i）有下面两种方案

• 将i拆分乘j和i-j的和，且i-j不再拆分成多个正整数 此时乘积是 j * (i-j)
• 将i拆分成j和i-j的和，且i-j还需拆分成多个正整数 此时乘积是 j * dp[i-j]

代码中嵌套的max的外层max是为了防止在内层j为循环变量的循环过程中覆盖掉原本dp[i]

因为有的时候两个数接近的时候乘积会比较大，但是一旦两个数数值相差较大的时候，就会变小，因此需要在每一次遍历的过程中保证dp[i]最大。

两层for循环是为了从前往后进行遍历

• 外层for的循环变量i从3开始 一直到n+1（开区间）
• 内存for的循环变量j从1开始 一直到i//2+1
  • j代表的是数字i可以从1开始进行拆分成j和i-j

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 // 2 + 1):
                dp[i] = max(dp[i], max(j* dp[i - j], j * (i - j)))
        return dp[-1]

Java代码

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i=3;i<=n;i++){
            for(int j=1;j<(int)i/2+1;j++){
                dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
}

96、不同的二叉搜索树（*）

dp[3] 表示1-3节点组成的二叉搜索树的个数，可以分成下面三种情况

元素1作为根结点的数量 = 右子树有2个元素的搜索树的个数 + 左子树有0个元素的搜索树的个数

元素2作为根节点的数量 = 右子树有1个元素的搜索树的个数 + 左子树有1个元素的搜索树的个数

元素3作为根节点的数量 = 右子树有0个元素的搜索树的个数 + 左子树有2个元素的搜索树的个数

dp[3] = 元素1作为根结点的数量 + 元素2作为根结点的数量 + 元素3作为根结点的数量

有两个元素的搜索树是dp[2]

[外链图片转存中…(img-K7LCBqNb-1712798807493)]

• 确定dp数组含义

dp[i] 表示1到i结点组成的二叉搜索树的个数为dp[i]

• 确定递推公式

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

j-1为j为头结点左子树节点数量，i-j为以j为头结点右子树节点数量

j相当于是头结点的元素，从1遍历到i结束（题目中说了这个二叉搜索树由n个节点1-n组成）

• dp数组如何进行初始化

dp[0] = 1 不能为0 否则在乘法运算中结果就是0了

空节点的二叉树也是一颗二叉搜索树

• 确定遍历顺序

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

416、分割等和子集（*）

本题需要判断数组中是否能够出现总和为sum/2的子集。这里需要有一个前提条件，如果数组的和为奇数是无法分成两个子集的，只有在数组和为偶数的情况下才能够划分两个子集。

所以可以根据这个条件先进行判断

sum_ = sum(nums)
if sum_ % 2 == 1:
    return False

转换为01背包问题，每个元素只能放入一次的问题是01背包，如果可以多次放入的话，属于完全背包问题。

• 背包的体积为sum/2，Python中是sum//2**【取整】**
• 背包放入的商品重量就是元素值，价值也是元素值
• 背包如果刚好装满，则找到总和为sum//2的子集
• 背包中的每一个元素是不可以重复放入的

背包容量是多少？本题中背包最大容量为sum//2

• dp数组含义

dp[j]表示容量为j的背包所能背的物品最大价值，这里的价值就是元素对应的值

本题中每个元素的元素值既是价值又是重量

dp[j]表示背包总容量是j，放进物品之后背的最大重量为dp[j]；

如果最后的dp[-1] == target 则满足题意

• 递推公式

01背包问题中，遍历到某个元素的时候，有两个原则，放与不放，递推公式是一致的。

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

• 初始化

dp[0] = 0，因为在容量为0的时候是无法放物品的

• 遍历顺序

外层循环遍历物品，遍历下标从1-n-1【Python范围1-n】，n为物品数量，本题中指数组长度len(nums)

内存循环遍历重量，遍历下标从target-nums[i]【【Python范围target-nums[i]-1】】，target为背包最大容量

如何将问题转换为01背包问题

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_ = sum(nums)
        if sum_ % 2 == 1:
            return False
        target = sum_ // 2
        dp = [0] * (target + 1)
        # 物品：nums 背包：target
        for num in nums:
            if num > target:
                return False
            for j in range(target, num - 1, -1):
                dp[j] = max(dp[j], dp[j - num] + num)
        # print(dp)
        return dp[target] == target

01背包相对于本题，主要要理解，题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是sum//2。

本题主要判断的是背包是否能够装满target

[外链图片转存中…(img-DQZxkeMs-1712798807494)]

优化版本：

本题如果上面的方法时间开销较大，可能存在一定的弊端，因此我们可以进行优化，优化的思路：

• 将原本存数字的dp数组转变为存储布尔值的数组
• 剪枝

布尔数组的初始化需要注意了，当j为0的时候，也就是背包容量为0的时候，需要赋值为True表示可以进行分割，否则后面都是False了

dp[j]表示容量为j的背包，是否能够分割成等和子集。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_ = sum(nums)
        if sum_ % 2 == 1:
            return False
        target = sum_ // 2  # 背包容量大小
        dp = [False] * (target + 1)
        dp[0] = True  
        for num in nums:
            if num>target:
                return False
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j-num]
        return dp[target]

[外链图片转存中…(img-twCeUsu8-1712798807495)]

1049、最后一块石头的重量II（*）

[外链图片转存中…(img-Obgn024x-1712798807495)]

题目含义是：尽量让石头分成重量相等的两堆，相撞之后剩下的石头最小。

本题中，物品重量为stones[i]，物品价值为stones[i]

最终需要返回的事剩余石头的最小重量，如果来可以分成相等的两堆，则说明没有返回值为0

• dp数组含义是什么？

dp[j]表示容量为j的背包可以背的最大重量是多少

• 递推公式是什么？

dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])

• 如何进行初始化？

背包的最大容量为sum(stones)//2

• 遍历顺序是什么？

# 外层循环遍历背包（即石头数组）
# 内存循环遍历重量

完整代码：

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        weight = total // 2
        dp = [0] * (weight + 1)
        for stone in stones:
            for j in range(weight, stone - 1, -1):
                dp[j] = max(dp[j], dp[j - stone] + stone)
        return total - 2 * dp[weight]

494、目标和（*）

分割等和子集 就是判断背包是否能装满

最后一块石头的重量II 就是看背包最大能装多少

本题就是看装满背包我们总共有多少种方式

本题中有几个先决条件，如果target大于nums数组的总和（当然target可能为负数所以这里加上绝对值），则没有这样的组合方式

本题中，我们假设全部为正的表达式值为left，全部为负的表达式值为right，则left+right=target，其中right=sum-left，可以得出left=(sum+target)/2，如果sum+target不为偶数则也没有这样的组合方式。

这里的背包容量大小是left大小，因为这里只需要计算组合方式，只需要算出left有多少种方式即可

问题转换为 装满容量为left的背包最多有多少种方法

本题也是计算有多少种方式，使用层层累加的形式。

• dp数组含义是什么？

装满容量为j的背包最多有dp[j]种方法

• 递推公式是什么？

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

• 如何进行初始化？

dp[0] = 1，根据递推公式，如果dp[0]为0，则后续所有的值都是0

• 遍历顺序是什么？

背包模板

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        sum_ = sum(nums)
        if abs(target)>sum_:
            return 0
        if (sum_+target)%2==1:
            return 0
        bagSize = (sum_+target)//2
        dp = [0] * (bagSize+1)
        dp[0] = 1
        for num in nums:
            for j in range(bagSize,num-1,-1):
                dp[j]+=dp[j-num]
        return dp[bagSize]

474、一和零（*）

[外链图片转存中…(img-lxWBbKvs-1712798807499)]

strs中的元素就是物品，m和n相当于两个背包，二维的01背包。

题目要求找出strs中的最大子集长度

• dp数组含义是什么？

有两个维度，本题中的m和n可以理解为一个背包，只不过这个背包是两个维度的

dp[i][j]表示最多有i个0和j个1的strs的最大子集的大小为dp[i][j]

• 递推公式是什么？

dp[i][j]可以由前一个字符串推出

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

dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

递推公式中的**+1**，加的是物品的数量

• 如何进行初始化？

如果物品的价格不会出现负数，就初始化为0即可，保证在后面递推的过程中不会出现覆盖

• 遍历顺序是什么？

先遍历物品再遍历背包

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0]*(m+1) for _ in range(n+1)]
        for s in strs:
            zero = s.count('0')  # 计算0的个数
            one = len(s)-zero    # 相减得到1的个数
            for i in range(n,one-1,-1):
                for j in range(m,zero-1,-1):
                    dp[i][j] = max(dp[i][j], dp[i-one][j-zero]+1)
        return dp[n][m]

上面的代码中使用s.count()方法时间复杂度还可以进行优化：使用collections模块中的内置Counter进行统计。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for i in range(m + 1)]
        for s in strs:
            zero = Counter(s)["0"]
            one = len(s) - zero
            for i in range(m, zero - 1, -1):
                for j in range(n, one - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1)
        return dp[m][n]

本题是给定背包容量，看装满背包之后有多少物品，求的是最大的物品数量，所以这里在递推公式中+1是加的物品数量

518、零钱兑换II（*）

本题属于完全背包问题，也就是跟01背包问题滚动数组的内层循环相异，需要从前往后进行遍历，所有面额的硬币都是可以进行重复选取的，所以这里的处理方式与01背包恰恰相反。

同时本题是求组合数的，方案之间是没有顺序的。组合问题在回溯中也是无序的。

本题是需要找有多少个这样的方案，所以应该是用层层累加的形式。

• dp数组含义是什么？

dp[i]表示表示凑成总金额为i的所有组合方案共有dp[i]种

• 递推公式是什么？

对于完全背包，并且是需要计算方案数有多少的题目，需要从前往后进行累加。因此递推公式如下所示：

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

• 如何进行初始化？

对于dp[0]，也就是全部凑成0，总共有一种方案也就是全部都不取，那么dp[0] = 1

• 遍历顺序是什么？

内层循环和外层循环都需要从前往后进行遍历。组合问题需要先遍历物品，再遍历背包。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for j in range(coin, amount + 1):
                dp[j] += dp[j - coin]
        return dp[-1]

377、组合总数IV

这里需要注意顺序不同的序列也被看做是不同的组合，所以这属于排列问题。

对于排列问题，for循环的嵌套顺序就有说法了

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

• dp数组含义是什么？

dp[j]表示组合和为j的共有dp[j]种

• 递推公式是什么？

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

• 如何进行初始化？

有递推公式可得，dp[0] = 1

• 遍历顺序是什么？

因为是排列问题，所以先遍历背包再遍历物品，注意这里需要处理num>j的情况。

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for j in range(target + 1):
            for num in nums:
                if num > j:
                    continue
                dp[j] += dp[j - num]

        return dp[-1]

完全背包问题之爬楼梯进阶版

完全背包问题，需要先遍历背包再遍历物品。

n,m = map(int,input().split())

dp = [0] * (n+1)
dp[0] = 1

for i in range(n+1):
    for j in range(1,m+1):
        if i-j<0:
            continue
        dp[i] += dp[i-j]
print(dp[-1])

322、零钱兑换

本题中，背包为amount，我们创建的dp数组的大小需要为amount+1

• dp数组含义是什么？

dp[j]表示凑成总金额数为j所需要的最少硬币数

• 递推公式是什么？

递推公式为dp[j] = min(dp[j], dp[j-coin] + 1)

• 如何进行初始化？

当j==0的时候需要的最少硬币为0，所以dp[0] = 0，对于除了0以外的dp数组，需要将其初始化为一个非负的最大值，所以这里全部初始化为最大值float("inf")

• 遍历顺序是什么？

完全背包问题，先遍历背包，在遍历物品

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # res = float("inf")
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0
        for j in range(amount + 1):
            for coin in coins:
                if j - coin < 0:
                    continue
                dp[j] = min(dp[j], dp[j - coin] + 1)
        return -1 if dp[-1] == float("inf") else dp[-1]

279、完全平方数

• dp数组含义是什么？

dp[i] 和为i的完全平方数的最少数量

• 递推公式是什么？

可以有两个维度推出dp[j]的值：

1. 维持不变dp[j]
2. 减去一个平方数的方案再加1，即dp[j-i*i]+1

dp[j] = min(dp[j], dp[j-i*i]+1)

• 如何进行初始化？

因为需要求最少数量，所以初始化的时候全部为float(“inf”)，而dp[0] = 0，表示平方数和为0的方案个数有0个

• 遍历顺序是什么？

先遍历背包，再遍历物品，本题中背包大小为n+1，物品是平方数

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float("inf")] * (n + 1)
        dp[0] = 0
        for j in range(n + 1):
            for i in range(1, int(j**0.5) + 1):
                dp[j] = min(dp[j], dp[j - i * i] + 1)
        return dp[n]

139、单词拆分

如何转换为背包问题？

拆分时可以重复使用字典中的单词，所以是完全背包问题。

字符串s是背包，物品是单词wordDict，同时对于示例二而言，apple+pen+apple和apple+apple+pen是不一样的，所以属于排列问题，需要先遍历背包，在遍历物品。

背包长度为：len(s)+1，物品为wordDict

• dp数组含义是什么？

dp[i] 表示字符串长度为i的话，dp[i]=true，表示可以拆分为一个或多个在字典中出现的单词

• 递推公式是什么？

只有在dp[j]为True的时候并且此时s[j:i]在wordDict中，dp[i]=True，然后直接break掉进入下一轮【只需要找到一种拆分方式即可】

• 如何进行初始化？

全部初始化为False，dp[0]赋值为True表示空字符串可以进行拆分

• 遍历顺序是什么？

属于排列问题，需要先遍历背包再遍历物品

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[0] = True

        for i in range(1, len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break

        return dp[-1]

198、打家劫舍

[外链图片转存中…(img-3ENiDajb-1712798807510)]

一层for循环往后进行遍历

• dp数组含义是什么？

dp[i]表示当前到第i家的为止，最多可以偷的最大的价值

• 递推公式是什么？

  • 偷第i家 dp[i] = dp[i-2]+nums[i]

  • 不偷第i家 dp[i] = dp[i-1]

• 如何进行初始化？

  • 第1位dp[0]初始值为nums[0]

  • 第2位dp[1]初始值为前两个数字中的最大值

• 遍历顺序是什么？

从前往后进行遍历

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        elif len(nums) == 2:
            return max(nums)
        dp = [0] * 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])
        # print(dp)
        return dp[-1]

优化版

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:  # 如果没有房屋，返回0
            return 0

        prev_max = 0  # 上一个房屋的最大金额
        curr_max = 0  # 当前房屋的最大金额

        for num in nums:
            temp = curr_max  # 临时变量保存当前房屋的最大金额
            curr_max = max(prev_max + num, curr_max)  # 更新当前房屋的最大金额
            prev_max = temp  # 更新上一个房屋的最大金额

        return curr_max  # 返回最后一个房屋中可抢劫的最大金额

213、打家劫舍II

本题的关键在于如何处理圆环问题，可以将1-n分成1-n-1和2-n这两个区间，然后在对应的区间使用打家劫舍中的方法去找到最大值即可。

• dp数组含义是什么？

dp[i]表示当前到第i家的为止，最多可以偷的最大的价值

• 递推公式是什么？

  • 偷第i家 dp[i] = dp[i-2]+nums[i]

  • 不偷第i家 dp[i] = dp[i-1]

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

• 如何进行初始化？

  • 第1位dp[0]初始值为nums[0]

  • 第2位dp[1]初始值为前两个数字中的最大值 max(nums[0], nums[1])

• 遍历顺序是什么？

class Solution:
    def rob(self, nums: List[int]) -> int:
        def myrob(nums):
            if len(nums) == 1:
                return nums[0]
            elif len(nums) == 2:
                return max(nums)
            dp = [0] * 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 dp[-1]

        if len(nums) == 1:
            return nums[0]
        elif len(nums) == 2:
            return max(nums)
        return max(myrob(nums[:-1]), myrob(nums[1:]))

class Solution:
    def rob(self, nums: List[int]) -> int:
        # 优化重复代码
        def robHouse(nums):
            n = len(nums)
            if n==0:
                return 0
            pre_max = 0
            cur_max = 0
            for num in nums:
                tmp = cur_max
                cur_max = max(pre_max+num,cur_max)
                pre_max = tmp
            return cur_max
        # 1-n-1 和2-n
        n = len(nums)
        if n==1:
            return nums[0]
        # elif n==2:
        #     return max(nums)
        nums1 = nums[:n-1]
        nums2 = nums[1:]
        dp1 = robHouse(nums1)
        # print(dp1)
        dp2 = robHouse(nums2)
        return max(dp1,dp2)

337、打家劫舍III

本题可以使用暴力算法进行求解，但求解的时候需要使用到后序遍历

动态规划解法：

dp数组表示的含义 下标为0表示不偷该节点得到的最大金钱，下标为1表示偷该节点得到的最大金钱

dp数组是一个长度为2的数组

递归三部曲

• 确定递归的参数和返回值

递归的参数是当前所遍历到的节点

返回值是长度为2的dp数组

• 确定终止条件

如果遍历到空节点，则返回[0, 0]

这也相当于dp数组的初始化

• 确定遍历顺序

后序遍历

通过递归左节点获得左节点偷与不偷的金钱

通过递归右节点获得右节点偷与不偷的金钱

// 下标0：不偷，下标1：偷
left = robTree(cur.left) // 左
right = robTree(cur.right) // 右
// 中

• 单层递归逻辑

如果偷当前结点的话，左右孩子结点就不能偷

val1 = cur.val + left[0] + right[0]

如果不偷当前结点的话，左右孩子结点就可以偷

val2 = max(left[0],left[1])+max(right[0], right[1])

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def traverse(node):
            if not node:
                return [0,0]
            left = traverse(node.left)
            right = traverse(node.right)
            # 不偷当前节点
            val1 = max(left[0],left[1])+max(right[0],right[1])
            # 偷当前节点
            val2 = node.val + left[0] + right[0]
            return [val1,val2]
        dp = traverse(root)
        return max(dp)

121、买卖股票的最佳时机（*）

贪心算法

贪心算法的思路就是取左边的最小值，然后每次计算当前值与当前最小值的差值，然后再取差值和res本身的最大值作为res值，直到循环结束，即得出最终结果。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 贪心算法  左边最小 右边最大
        min_ = float("inf")
        res = 0
        for p in prices:
            min_ = min(min_,p)
            res = max(res,p-min_)
        return res

动态规划

• dp数组含义是什么？

和打家劫舍III一样，本题中的dp数组只有两列，所代表的含义如下： 二维dp数组

dp[i][0]表示第i天持有股票所得最多现金

dp[i][1]表示第i天不再持有股票最多现金

• 递推公式是什么？

dp[i][0]表示如果第i天持有股票，可以由两个状态推导出来：

• 第i-1天就持有股票，则维持现状，即dp[i-1][0]

• 第i-1天没有持有股票，第i天需要买入，所得现金就是买入今天股票的现金：-price[i]

那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

dp[i][1]表示：第i天不再持有股票，可以由两个状态推导出来：

• 第i-1天已经出售股票，维持现状，dp[i][1] = dp[i-1][1]
• 第i天出售股票，就按照今天的价格卖出股票后得到的现金，也就是第i-1天持有股票的现金加上i天卖出股票的价格，dp[i][1] = dp[i-1][0]+prices[i]

dp[i][1]也应该选择现金大的，所以dp[i][1] = max(dp[i - 1][1], dp[i-1][0]+prices[i]);

• 如何进行初始化？

初始化的时候，dp[0][0]=-prices[0]表示第0天持有股票的现金，dp[0][1] = 0，股票还没卖所以为0

• 遍历顺序是什么？

因为后面的状态依赖于前面的状态，所以便利的顺序是从前往后进行遍历

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 动态规划
        n = len(prices)
        dp = [[0,0] for _ in range(n)]
        dp[0][0] = -prices[0]
        for i in range(1,n):
            dp[i][0] = max(dp[i-1][0], -prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
        return dp[-1][1]

使用滚动数组来节省空间（上面的二维数组其实有很多空间都是浪费的）

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 动态规划
        n = len(prices)
        dp0 = -prices[0]
        dp1 = 0
        for i in range(1,n):
            dp0 = max(dp0, -prices[i])
            dp1 = max(dp1, dp0+prices[i]) # 因为dp0始终是小于dp1的，所以这里使用更新后的dp0也不会有影响
        return dp1

122、买卖股票的最佳时机II（*）

[外链图片转存中…(img-GZ54Q9WL-1712798807514)]

这道题在贪心算法章节已经使用贪心算法解决问题，贪心算法的核心思想就是将差值中的正值作为利润累加起来，出现负值则不作更新。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 贪心算法
        res = 0
        for i in range(1,len(prices)):
            res += max(0,prices[i]-prices[i-1])
        return res

这里使用动态规划进行求解

本题中的股票是可以多次买入和出售的，在第i天买入股票的时候，所持有的现金可能会包含之前买卖过的利润。

第i天如果买入股票，所的现金就是昨天不持有股票所得的现金今天的股票价格

dp[i-1][0] - prices[i]

本题可以多次进行股票的买卖，但是最多持有一只股票

• dp数组含义是什么？

dp数组的含义与上一题一致

**dp[i][0]**表示第i天持有股票的最多现金

**dp[i][1]**表示第i天不持有股票所得最多现金

• 递推公式是什么？

dp[i][0] 如果在第i天买入股票，所得现金就是昨天不持有股票的金额减去今天股票的价格（这是本题的核心）

在上一个问题中，买入股票的时候因为只能进行一次交易，所以等价于用0-prices[i]，而在本题中实际上是用第i-1天手中不持有现金的情况下减去今天的股票价格，就是当前持有股票的现金。

dp[i][0]可以从两个维度上进行推导

• 第i-1天就持有股票，维持状态，拥有的金额为dp[i-1][0]
• 第i-1天不持有股票，第i天买入股票，拥有的金额为第i-1天不拥有股票的金额减去股票价格，dp[i][0] = dp[i-1][1] - prices[i]

dp[i][0] = max(dp[i-1][1], dp[i-1][1]-prices[i])

dp[i][1]的递推公式同上题 从两个状态得出，第i-1天就不持有股票以及第i天卖出股票即前一天持有股票拥有的最大现金加上当天的股票价格

dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])

• 如何进行初始化？

dp[0][0]表示持有股票拥有的现金 初始化为-prices[0]

dp[0][1]表示不持有股票拥有的现金 初始化为0 即一开始啥都没有

• 遍历顺序是什么？

从前往后

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

上面的代码中，使用二维数组的方式就会导致很多层的空间浪费，导致不必要的性能开销，因此可以使用滚动数组进行优化。

使用滚动数组

• dp0代表持有股票拥有的最大现金
• dp1代表不持有股票拥有的最大现金

# 使用滚动数组版本
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp0 = -prices[0]
        dp1 = 0
        for i in range(1,len(prices)):
            dp0 = max(dp0,dp1-prices[i])
            dp1 = max(dp1,dp0+prices[i]) # 因为dp0始终是小于dp1的，所以这里使用更新后的dp0也不会有影响
        return dp1

123、买卖股票的最佳时机III（*）

题目中说了最多可以完成两笔交易，即可以只交易一次，或者交易两次

同时不能同时参与多笔交易，即最多手里只能有持有一次股票

• dp数组含义是什么？

共有五个状态：尚未进行操作的状态、第一次持有股票、第一次卖出股票、第二次持有股票、第二次卖出股票

dp[i][0]-dp[i][4] 分别表示

dp[i][j] 表示第i天在状态j下所拥有的最大现金

• 递推公式是什么？

**dp[i][1]**可以从两个方面推导出来：

第i天买入股票，dp[i][1] = dp[i-1][0] - prices[i]

第i天没有操作（即第i-1天已经持有股票了），dp[i][1] = dp[i-1][1]

根据上一题的经验，我们需要在这两者中选取最大值，即dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])

dp[i][2] 表示第i天第一次不再持有股票拥有的最大现金，同样可以从两个方向推导：

第i天卖出股票，拥有的金额为前一天不拥有股票的现金加上今天的股票价格，即dp[i][2] = dp[i-1][1] + prices[i]

第i-1天卖出股票，维持前一天状态，dp[i][2] = dp[i-1][2]

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

同理当j=3和j=4的时候的递推公式如下

dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])

dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])

• 如何进行初始化？

第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;

第0天做第一次买入的操作，dp[0][1] = -prices[0];

第0天做第一次卖出的操作，这个初始值应该是多少呢？

此时还没有买入，怎么就卖出呢？ 其实大家可以理解当天买入，当天卖出，所以dp[0][2] = 0;

第0天第二次买入操作，初始值应该是多少呢？应该不少同学疑惑，第一次还没买入呢，怎么初始化第二次买入呢？

第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后再买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。

所以第二次买入操作，初始化为：dp[0][3] = -prices[0];

同理第二次卖出初始化dp[0][4] = 0;

• 遍历顺序是什么？

从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

以输入[1,2,3,4,5]为例

最后我们应该选择第二次卖出股票持有的最大现金作为我们的返回值

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 五个状态 0 1 2 3 4分别表示
        n = len(prices)
        dp = [[0, 0, 0, 0, 0] for _ in range(n)]
        # 初始化
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        dp[0][2] = 0
        dp[0][3] = -prices[0]
        dp[0][4] = 0
        for i in range(1, n):
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])
        return dp[-1][-1]

其实状态1是可以省略的

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 五个状态 0 1 2 3 4分别表示
        n = len(prices)
        dp = [[0, 0, 0, 0] for _ in range(n)]
        # 初始化
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        dp[0][2] = -prices[0]
        dp[0][3] = 0
        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], - prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i])
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i])
        return dp[-1][-1]

使用滚动数组

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [-prices[0], 0, -prices[0], 0]
        for i in range(1, len(prices)):
            dp[0] = max(dp[0], -prices[i])
            dp[1] = max(dp[1], dp[0] + prices[i])
            dp[2] = max(dp[2], dp[1] - prices[i])
            dp[3] = max(dp[3], dp[2] + prices[i])
        return dp[3]

188、买卖股票的最佳时机IV（*）

本题是上一题的扩展版本，本题中可以进行k次购买，k次出售，所以状态的个数也是一个变量，总共的状态数为2*k

• dp数组含义是什么？

0表示第一次买入股票持有的最大现金

1表示第一次卖出股票持有的最大现金

2表示第二次买入股票持有的最大现金

3表示第二次卖出股票持有的最大现金

…

以此类推，即i为偶数表示买入股票持有的最大现金，i为奇数表示卖出股票持有的最大现金

• 递推公式是什么？

用for循环代替掉上一题的最多两次买卖，也就是说上一题中最多两次买卖其实本质上也就是本题中k=2

这里需要进行特殊处理的是dp[0]的值，dp[0]的值有两个维度获取：

1. 前一天就持有股票，继续维持状态，dp[0] = dp[0]
2. 前一天不持有股票，需要买入股票，但是手中的资金为0，dp[0] = -prices[i]

即dp[0] = max(dp[0], -prices[i])

对于其余的为偶数次的持有股票状态，可以就需要用前一天不持有股票的金额减去当天的股票价格了，这部分可以直接用一个for循环统一处理。

for j in range(1, 2 * k):
    if j % 2 == 0:
        dp[j] = max(dp[j], dp[j - 1] - prices[i])
    else:
        dp[j] = max(dp[j], dp[j - 1] + prices[i])

• 如何进行初始化？

在进行初始化的时候，需要设置为偶数的状态值为-prices[0]，即持有股票的状态

• 遍历顺序是什么？

后一个状态依赖于前一个状态因此需要从前往后进行遍历

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        dp = [0] * (2 * k)
        for i in range(2 * k):
            if i % 2 == 0:
                dp[i] = -prices[0]
        # print(dp)
        for i in range(1, len(prices)):
            dp[0] = max(dp[0], -prices[i])
            for j in range(1, 2 * k):
                if j % 2 == 0:
                    dp[j] = max(dp[j], dp[j - 1] - prices[i])
                else:
                    dp[j] = max(dp[j], dp[j - 1] + prices[i])
        return dp[-1]

309、买卖股票的最佳时机含冷冻期

本题和之前的区别卖出股票之后，无法再第二天立即购买股票（中间有一个冷冻期1天）

确认共计多少种状态：

• 状态1：持有股票状态（今天买入股票或者前几天就已经持有股票了）
• 不持有股票的状态（分成两种情况）
  • 状态2：保持卖出股票的状态（两天之前就已经卖出股票了并且度过了一天的冷冻期。或者前一天就卖出股票一直没有操作） 区别于冷冻期，即非冷冻期
  • 状态3：今天卖出股票
• 状态4：今天为冷冻期，冷冻期只有一天，冷冻期进行单独处理

这里状态对应数组的下标为0123

• dp数组含义是什么？

dp[i][j] 其中i表示第几天，j表示状态（即状态1-状态4）

• 递推公式是什么？

对于状态1，即dp[i][0]，表示持有股票状态

其值涉及到两个操作

操作1：前一天就已经持有股票了，dp[i][0] = dp[i-1][0]

操作2：今天买入股票

• 前一天是冷静期 dp[i][0] = dp[i-1][3] - prices[i]
• 前一天是保持卖出股票状态 dp[i][0] =dp[i-1][1] -prices[i]

所以dp[i][0] = max(dp[i-1][0], dp[i][3]-prices[i], dp[i-1][1] -prices[i])

对于状态2，即dp[i][1] 表示保持卖出股票的状态

• 前一天为冷冻期 dp[i][1] = dp[i-1][3]
• 仍然是保持卖出股票状态dp[i][1] = dp[i-1][1]

dp[i][1] = max(dp[i-1][1], dp[i-1][3])

对于状态3，即dp[i][2] 表示今天卖出股票的状态

可以从1个方向推导出来 即前一天持有股票

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

对于状态4，即dp[i][3] 表示今天是冷冻期，即前一天刚卖出股票

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

• 如何进行初始化？

对于第0天，如果是持有股票状态即当天买入股票

如果是保持卖出股票状态，dp[0][1] = 0

如果是今天卖出股票状态

• 遍历顺序是什么？

后面的状态依赖于前面的状态，因此需要从前往后进行遍历

使用二维数组的版本

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0]*4 for _ in range(n)]
        dp[0][0] = -prices[0]
        for i in range(1,n):
            # 状态1：持有股票状态 ①前一天就持有 ②前一天为冷冻期购入 ③前一天是不持有股票状态购入
            dp[i][0] = max(dp[i-1][0], dp[i-1][3]-prices[i],dp[i-1][1]-prices[i])
            # 状态2：不持有股票状态 （区别于冷冻期 表示2天前卖出股票或者更久）
            dp[i][1] = max(dp[i-1][3],dp[i-1][1])
            # 状态3：卖出股票状态 前一天持有股票
            dp[i][2] = dp[i-1][0] + prices[i]
            # 状态4：冷冻期
            dp[i][3] = dp[i-1][2]
        return max(dp[-1])

使用一维数组的错误版本：在下面这份代码中，有个错误就是在状态3（下标为2）和状态4（下标为3）的时候，使用的dp[0]和dp[2]已经被修改成本轮的最新值了，而实际上我们应该使用尚未修改的版本，因此需要使用两个变量来记录之前的dp[0]和dp[2]就可以得到正确的结果了。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [-prices[0],0,0,0]
        for i in range(1,len(prices)):
            # 状态1：持有股票状态
            dp[0] = max(dp[0],dp[3]-prices[i],dp[1]-prices[i])
            # 状态2：保持卖出股票状态
            dp[1] = max(dp[3],dp[1])
            # 状态3：卖出股票
            dp[2] = dp[0]+prices[i]
            # 状态4：冷冻期
            dp[3] = dp[2]
        return max(dp)

修改后的代码如下：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [-prices[0],0,0,0]
        for i in range(1,len(prices)):
            # 状态1：持有股票状态
            tmp_dp0 = dp[0]
            dp[0] = max(dp[0],dp[3]-prices[i],dp[1]-prices[i])
            # 状态2：保持卖出股票状态
            dp[1] = max(dp[3],dp[1])
            # 状态3：卖出股票
            tmp_dp2 = dp[2]
            dp[2] = tmp_dp0+prices[i]
            # 状态4：冷冻期
            dp[3] = tmp_dp2
        return max(dp)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp1 = -prices[0]  # 持有股票 | 今天买入或前几天就持有
        dp2 = 0  # 不持有股票 | 刚好度过了一天冷冻期或者卖出超过2天了
        dp3 = 0  # 不持有股票 | 今天卖出股票
        dp4 = 0  # 冷冻期 |
        for i in range(1, len(prices)):
            tmp = dp1
            dp1 = max(dp1, dp2 - prices[i], dp4 - prices[i])  #
            dp2 = max(dp2, dp4)
            tmp3 = dp3
            dp3 = tmp + prices[i]
            dp4 = tmp3
        return max(dp2, dp3, dp4)

[外链图片转存中…(img-whMPtOLS-1712798807521)]

714、买卖股票的最佳时机含手续费

本题与买卖股票的最佳时机II的区别就在于每次在进行卖出股票的时候需要一笔手续费，所以只需要在交易的时候减去fee即可，其余的内容不需要做任何修改。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        # 状态1：今天持有股票拥有的最大现金
        # 状态2：今天不持有股票拥有的最大现金
        dp1 = -prices[0]
        dp2 = 0
        for i in range(1, len(prices)):
            dp1 = max(dp1, dp2 - prices[i])
            dp2 = max(dp2, dp1 + prices[i] - fee)
        return dp2

300、最长递增子序列

[外链图片转存中…(img-DdZluOHM-1712798807523)]

在回溯算法章节，有一题递增子序列的题目，但是的相关题目中有本题，我也尝试采用回溯算法解决该题，测试用例AC了，但是全部测试用例超时了，代码如下：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        res = 0

        def backtracking(startindex, path):
            nonlocal res
            if startindex > len(nums):
                return
            if len(path) >= 1:
                res = max(res, len(path))
            uset = set()
            for i in range(startindex, len(nums)):
                if (path and path[-1] >= nums[i]) or nums[i] in uset:
                    continue
                uset.add(nums[i])
                path.append(nums[i])
                backtracking(i + 1, path)
                path.pop()

        backtracking(0, [])
        return res

本题实际上应该采用动态规划算法进行求解。回溯算法可以求解除所有的方案出来，但是时间复杂度也更高。

这里的递增子序列的含义就是说可以从这个数组中抽出来一些数字组成一个递增的子序列即可。不要求这个子序列一定是连续的

对于子序列问题，我们通常是可以采用动态规划来解决的

• dp数组含义是什么？

dp[i]表示下标i之前包括i在内的以nums[i]结尾的最长递增子序列的长度

• 递推公式是什么？

位置i的最长上升子序列等于j从0到i-1各个位置上的最长上升子序列+1的最大值。只有在值递增的情况下才会进行最大值的更新

if (nums[i] > nums[j]):
    dp[i] = max(dp[i],dp[j]+1)

在进行比较的时候需要和前面所有的进行对比，也就是要取0到i-1中的全部最大值

• 如何进行初始化？

dp[i]的初始值大小至少都是1，所以初始化一个全为1的一维数组即可，数组长度为n，如果全部初始化为0的话，会导致最终结果不对，初始化为1的含义也表示从当前下标nums[i]为结尾的递增子序列长度为1

• 遍历顺序是什么？

dp[i] 是0到i-1各个位置的最长递增子序列推导出来的，所以从前往后进行遍历

j从0遍历到i-1，遍历i在外层循环，遍历j在内层循环

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)
        res = 1
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
            res = max(dp[i], res)
        # print(dp)
        return res

674、最长连续递增序列

这题与上一题的区别就在于要求这个序列必须在原来的数组中是连续的。连续的情况下，子序列只跟前一个状态有关。如果是不连续的话，状态就会跟前面的最大值有关（即前i-1个状态）

• dp数组含义是什么？

dp[i]表示下标i之前包括i在内的以nums[i]结尾的最长连续递增子序列的长度

• 递推公式是什么？

这里的区别就是，如果出现隔断了，那么就需要重置临时的最大长度为1重新进行统计

本题不需要进行两层循环，一层循环即可，如果nums[i] > nums[i-1] 那么dp[i] = dp[i-1]+1，否则dp[i] = 1

• 如何进行初始化？

跟上一题一样，初始化都为1。表示从自己开始的话最长连续子序列为1

• 遍历顺序是什么？

后面的状态依赖于前面的，所以是从前往后进行遍历，因为这里下标处理的时候涉及到i-1，所以需要从1开始进行循环，到len(nums)为止。

方法1: 贪心算法

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        res = 1  # 用来记录最大值
        tmp = 1  # 临时变量 如果出现不连续的情况tmp重置为1
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                tmp += 1
                res = max(res, tmp)
            else:
                tmp = 1  # 重新开始进行计算
        return res

方法2：动态规划

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)
        res = 1
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                dp[i] = dp[i - 1] + 1
                res = max(res, dp[i])
        return res

718、最长重复子数组

本题的含义就是找出两个数组中重复部分的最大长度，数组子序列的问题，采用动态规划算法进行求解。本题中的子数组是要求连续的

• dp数组含义是什么？

dp[i][j]表示nums1数组下标1到i-1和nums2数组下标1到j-1的重复部分的最大长度（必须是连续的）

dp[i][j] 这里的i，j需要从1开始

• 递推公式是什么？

本题中，dp[i][j]只能通过其状态的左上方的值获取，即dp[i][j] = dp[i-1][j-1] + 1 这里为什么只能从左上方递推过来？

if nums1[i-1] == nums2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1

• 如何进行初始化？

n1 = len(nums1)
n2 = len(nums2)
dp = [[0]*(n2+1) for _ in range(n1+1)]

• 遍历顺序是什么？

先遍历nums1后遍历num2，其实顺序是无所谓的。

二维DP代码如下：

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        n1 = len(nums1)
        n2 = len(nums2)
        dp = [[0] * (n1 + 1) for _ in range(n2 + 1)]
        res = 0
        for i in range(1, n2 + 1):
            for j in range(1, n1 + 1):
                if nums1[j - 1] == nums2[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                res = max(res, dp[i][j])
        return res

本题中所有的状态都是从左上角推导出来的，因此可以进行状态压缩，同时其中只保存一个数据，不会发生覆盖的情况。另外需要注意，如果nums2依旧从前往后进行遍历的时候可能会因为过程中的更新导致答案错误，所以nums2需要从后往前进行遍历。

这里需要注意的是，最大值的答案很可能是在遍历过程中产生的，后续会将其进行覆盖，所以需要在比较的过程中记录下最大值最终返回

一维DP代码如下：

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        # 创建一个一维数组 dp，用于存储最长公共子数组的长度
        dp = [0] * (len(nums2) + 1)
        # 记录最长公共子数组的长度
        result = 0

        # 遍历数组 nums1
        for i in range(1, len(nums1) + 1):
            # 用于保存上一个位置的值
            prev = 0
            # 遍历数组 nums2
            for j in range(1, len(nums2) + 1):
                # 保存当前位置的值，因为会在后面被更新
                current = dp[j]
                # 如果 nums1[i-1] 和 nums2[j-1] 相等
                if nums1[i - 1] == nums2[j - 1]:
                    # 在当前位置上的最长公共子数组长度为上一个位置的长度加一
                    dp[j] = prev + 1
                    # 更新最长公共子数组的长度
                    result = max(result,dp[j])
                else:
                    # 如果不相等，将当前位置的值置为零
                    dp[j] = 0
                # 更新 prev 变量为当前位置的值，供下一次迭代使用
                prev = current

        # 返回最长公共子数组的长度
        return result

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        res = 0
        n1 = len(nums1)
        n2 = len(nums2)
        dp = [0] * (n2 + 1)
        for i in range(1, n1 + 1):
            prev = 0
            for j in range(1, n2 + 1):
                current = dp[j]
                if nums1[i - 1] == nums2[j - 1]:
                    dp[j] = prev + 1
                    res = max(res, dp[j])
                else:
                    dp[j] = 0
                prev = current
            # print(dp)
        return res

[外链图片转存中…(img-9NO7wkpY-1712798807528)]

拓展

本题我们下标统一规定了从1开始，这样的目的是方便我们进行后续的递推，省去了一步初始化的步骤。如果需要从0开始，就需要对第一行和第一列进行特殊的初始化，这样比较麻烦。相等的地方需要赋值为1。

114、最长公共子序列（*）

[外链图片转存中…(img-4GxVjkhz-1712798807528)]

本题与上一题最长重复子数组的区别就在于，这里不需要连续，只需要是相对连续的即可

• dp数组含义是什么？

dp[i][j] 表示字符串text1下标从0到i-1和字符串text2下标从0到j-1的最长公共子序列的长度

• 递推公式是什么？

从三个方向递推过来

如果text1[i-1]和text2[j-1]相等，则dp[i][j]=dp[i-1][j-1] + 1 在二维dp中可以看做是从左上角递推过来的

如果两者不相等，则需要考虑从其左侧或者正上方递推过来。即dp[i][j] = max(dp[i][j-1], dp[i-1][j])

不相等的情况是使用前面字符的最长公共子序列 假装删除其中一个字符 可以是i-1位置的也可能是j-1位置上的

• 如何进行初始化？

初始化为0，即不需要进行单独的处理，dp数组在创建的时候，就是全0的数组。不需要考虑其他额外的情况！

• 遍历顺序是什么？

从前往后进行遍历，总共有三个方向可以推导出dp[i][j]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n1 = len(text1)
        n2 = len(text2)
        dp = [[0] * (n1 + 1) for _ in range(n2 + 1)]
        for i in range(1, n2 + 1):
            for j in range(1, n1 + 1):
                if text2[i - 1] == text1[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

一维dp数组

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        t1 = len(text1)
        t2 = len(text2)
        dp = [0]*(t2+1)
        for i in range(1,t1+1):
            prev = 0
            for j in range(1,t2+1):
                current = dp[j]
                # print(current)
                if text1[i-1]==text2[j-1]:
                    dp[j] = prev + 1  # 0+1   保留上一行的值
                else:
                    dp[j] = max(dp[j],dp[j-1])
                prev = current
            # print(dp)
        return dp[-1]     

1035、不相交的线

[外链图片转存中…(img-odlXjSoW-1712798807531)]

本题的本质和最长公共子序列是一样的，代码可以原封不动不做修改，仅需修改变量

题目给出的连线的条件是nums1[i-1]==nums2[j-1]则可以进行连线，必须要保持相对的顺序，否则会出现线的交叉导致出错。

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        n1 = len(nums1)
        n2 = len(nums2)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

53、最大子数组和

法一：贪心算法

贪心的思路就是不断进行累加，如果出现负值了，就重新开始记数，同时在每一轮进行最大值的更新，出现比当前最大值大了才进行更新。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = float("-inf")
        tmp = 0
        for num in nums:
            tmp += num
            res = max(res, tmp)
            if tmp < 0:
                tmp = 0
        return res

法二：动态规划

动规五部曲：

• dp数组含义是什么？

dp[i]表示到当前下标i位置的最大子数组和是多少

• 递推公式是什么？

有两个方向可以推导出最终结果

一个是dp[i-1]+nums[i] ，表示当前值和前面的累加

一个是当前值大于前面值的累加和，赋值为nums[i]

• 如何进行初始化？

将dp[0]赋值为nums[0]即可，从下标为1开始

• 遍历顺序是什么？

从前往后进行遍历即可

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0]*n
        dp[0] = nums[0]
        # 两个状态   累加前面的和或者当前值从新开始
        for i in range(1,n):
            dp[i] = max(dp[i-1]+nums[i], nums[i])
        # print(dp)
        return max(dp)

392、判断子序列

[外链图片转存中…(img-dmSNlPoy-1712798807535)]

解法一：双指针法

双指针解法的思路是：使用两个指针分别来对字符串s和字符串t进行遍历，如果当前位置的s[s_]==t[t_]，则s_+1，在每一轮循环的过程中t_都是需要加1的。

如果循环结束的时候，字符串s的长度s_和len(s)相等，则表示s是t的子序列

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # 使用双指针来解决
        if s and not t:
            return False
        s_ = t_ = 0
        while s_ < len(s) and t_ < len(t):
            if s[s_] == t[t_]:
                s_ += 1
            t_ += 1
        return s_ == len(s)

解法二：动态规划

本题中只需要考虑删除元素的情况，不需要考虑添加元素的情况因此还是比较简单的 【编辑距离的入门题目】

只需要判断二者的公共子序列长度是否为s的长度即可

• dp数组含义是什么？

dp[i][j]表示以下标为i-1为结尾的字符串s和以下标为j-1结尾的字符串t，相同子序列的长度

• 递推公式是什么？

分为两种情况：

1. s[i-1]==t[j-1] 即t中找到了一个字符在s中出现了

2. s[i-1]!=t[j-1] 相当于t要删除元素，并继续进行匹配

对于情况一，dp[i][j] = dp[i-1][j-1] + 1 表示找到了相同子序列，长度加1即可

对于情况二，dp[i][j] = dp[i][j-1] 表示字符串t删掉一个字符，因为是判断s是否是t的子序列，所以不能对s进行删除操作

• 如何进行初始化？

初始化还和之前一样赋值为0即可

• 遍历顺序是什么？

从前往后进行遍历

[外链图片转存中…(img-e9gdr0TV-1712798807537)]

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        n1 = len(s)
        n2 = len(t)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = dp[i][j - 1]
        return n1 == dp[-1][-1]  # 即公共子序列的长度为s的长度n1

115、不同的子序列(**)

[外链图片转存中…(img-9ql526hQ-1712798807538)]

• dp数组含义是什么？

dp[i][j]的含义是字符串s以i-1结尾的子序列出现在以j-1为结尾的字符串t的个数为dp[i][j]

• 递推公式是什么？

这里的递推公式是这样的（分为两种情况）：

如果两个字符相等，则dp[i][j]由两个部分组成：dp[i-1][j-1] 和 dp[i-1][j]

dp[i-1][j-1]表示使用s[i-1]和t[j-1]进行比较或者不使用s[i-1]而使用s[i-2]进行比较，模拟把这个s[i-1]这个元素给删除了

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

前一个有多少种方式+s删掉s[i-1]这个字符再进行比较出现的次数。因为题目问的是s的子序列中有多少个t，所以t不需要删除元素而s可以删除

这里的问题是dp[i-1][j-1]中是否囊括了dp[i-1][j]的值？

例如s=bagg，t=bag，再进行判断的时候，s[2]和s[3]是相等的，所以这两者可以取其中一个就可以组成bag了，共有两种方案

如果s[i-1]和t[j-1]不相等，dp[i][j] = dp[i-1][j]，表示删除s中的j-1字符，用s[i-2]进行比较

• 如何进行初始化？

在dp数组初始化的时候我们赋值为全0数组

但是在j=0的时候，即t为空字符串的时候，s删除所有的字符就可以构成t了，此时dp[i][0]=1，即有s有一个子字符串为t

所以需要对dp数组进行的初始化是将第一列的所有值都赋值为1

for i in range(len(s)):
    dp[i][0] = 1

• 遍历顺序是什么？

从前往后进行遍历，但是需要注意，需要保证j大于1。有递推公式可以得出dp[i][j]是从左上方和正上方推出来的。

• 距离推导dp数组

以s：“baegg”，t："bag"为例，推导dp数组状态如下：

[外链图片转存中…(img-RwVU2xSY-1712798807540)]

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n1 = len(s)
        n2 = len(t)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        for i in range(n1):
            dp[i][0] = 1
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else: # 模拟删除字符串s[i-1] 用s[i-2]进行比较
                    dp[i][j] = dp[i - 1][j]
        return dp[-1][-1]

583、两个字符串的删除操作（*）

[外链图片转存中…(img-NFfVE4z2-1712798807542)]

本题不同于上一题不同的子序列，两个单词word1和word2都可以进行删除操作。

注意：本题中仅涉及到删除操作

方法一：正向思路

• dp数组含义是什么？

dp[i][j] 表示以i-1为结尾的字符串word1和以j-1为结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

• 递推公式是什么？

• word[i-1]与word[i-1]相等，则不需要删除字符维持不变即可

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

• word[i-1]与word[i-1]不相等，有如下几种情况

  • 删除word1[i-1]，最少操作次数为dp[i-1][j] + 1
  • 删除word2[j-1]，最少操作次数为dp[i][j-1] + 1
  • 删除word1[i-1]和word2[i-1]，最少操作次数为dp[i-1][j-1] + 2

本题求的是最少的操作次数，因此需要取这三者中的最小值，即min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 2)。

但是dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2

这里解释一下为什么

因为dp[i][j] 表示以i-1为结尾的字符串word1和以j-1为结尾的字符串word2，想要达到相等，所需要删除元素的最少次数，所以dp[i][j-1]和dp[i-1][j-1]的区别就在于多一个字符串，可以理解为dp[i]][j-1]=dp[i-1][j-1]+1，即需要多删除一个字符串所以要在这个基础上加1

• 如何进行初始化？

dp[i][0]表示以i-1结尾的word1要想变成空字符串，需要删除的字符串个数为i，所以dp[i][0] = i

dp[0][j] 同理 dp[0][j] = j

• 遍历顺序是什么？

从前往后进行遍历

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        for i in range(n1 + 1):
            dp[i][0] = i
        for j in range(n2 + 1):
            dp[0][j] = j
        # print(dp)
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2)
        # print(dp)
        return dp[-1][-1]

方法二：逆向思路

本题的另一个思路是求两个字符串的最长公共子序列，然后用长度之和减去两倍的最长公共子序列。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        # print(dp)
        return n1 + n2 - 2 * dp[-1][-1]

72、编辑距离(*)

本题跟之前的题目相比，多了两个操作（插入和替换单词），其中插入一个单词等价于将多的那个字符串增加一个字符，所以这个可以不用单独考虑。而替换单词需要进行考虑将其中一个字符串的当前字母替换为另一个字符串的当前字母。

• dp数组含义是什么？

dp[i][j]表示以i-1结尾的word1和以i-1结尾的word2，如果想要变成一样的字符需要的最少操作次数

• 递推公式是什么？

如果word1[i-1]和word2[j-1]相等，则不需要进行操作，即dp[i][j]=dp[i-1][j-1]

如果word1[i-1]和word2[j-1]不相等，需要进行的操作有

• 增
  • 选择增加的时候，本质上和删除的操作次数是一样的
• 删
  • 如果删除的是word1的第i-1位置，则dp[i][j] = dp[i-1][j] + 1
  • 如果删除的是word2的第j-1位置，则dp[i][j] = dp[i][j-1] + 1
• 替换位置
  • 替换的时候，即替换word1[i-1]和word2[j-1]其中之一使其相等，dp[i][j] = dp[i-1][j-1] + 1

所以dp[i][j]=min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)

• 如何进行初始化？

初始化的时候需要注意dp[0][j]和dp[i][0]的含义

dp[0][j] 表示word2要变成word1空字符串需要操作的次数，即为j次

dp[i][0] 表示word1要变成word2空字符串需要操作的次数，即为i次

• 遍历顺序是什么？

从前往后进行遍历

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        # 初始化
        for i in range(n1+1):
            dp[i][0] = i
        for j in range(n2+1):
            dp[0][j] = j
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1)
        # print(dp)
        return dp[-1][-1]

[外链图片转存中…(img-CVPWqifa-1712798807545)]

647、回文子串(*)

子串：连续的字符串组成的一个序列

统计字符串s中的回文子串的数目，本题求解的是数量

• dp数组含义是什么？

dp[i]如果表示到下标i位置字符串s的子串有多少个回文子串，那么就很难找到递推关系

所以dp数组初始化为dp[i][j] 字符串从i到j的子串是否是回文子串 这里用bool类型的元素来进行表示即可

• 递推公式是什么？

如果s[i]和s[j]相等，则分成三种情况讨论

• i==j，单个字符，是回文子串
• j-i=1，即j和i相差1个字符，也是回文子串
• j-i≥1，相差多个字符，就需要看中间的字符是否也是回文子串，即dp[i+1][j-1]

如果s[i]和s[j]不相等，则直接保持默认的情况False即可

• 如何进行初始化？

初始化全部的dp数组为false，表示不是回文子串，dp数组的大小为一个二维矩阵，长和宽分别为n

• 遍历顺序是什么？

从下图可以知道，当前值依赖于左下角的值，所以遍历的顺序一定是从dp数组左下角到右上角的

从dp左下角往右上角递推，注意j是从i开始进行遍历一直到len(s)的

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        res = 0
        dp = [[False] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j]:
                    if j - i <= 1:
                        res += 1
                        dp[i][j] = True
                    else:
                        if dp[i + 1][j - 1]:
                            res += 1
                            dp[i][j] = True
            # print(dp[i])
        return res