快站app下载,wordpress菜单 链接地址,这么做输入文字的网站,攻击网站的方法所有题目均来自于LeetCode#xff0c;刷题代码使用的Python3版本 动态规划 问题分类
如果某一个问题有重叠的子问题#xff0c;则使用动态规划进行求解是最有效的。
动态规划中每一个状态一定是由上一个状态推导出来的#xff0c;这一点区别于贪心算法
动态规划五部曲
确… 所有题目均来自于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]);
并且需要注意如果jweight[i]的时候是不能放物品的因为这样的情况是无法作为数组的下标的。
放物品时候的理解当i放进去的时候背包的总重量为j前i-1个能放的物品剩余重量就只剩下j-weight[i]前i-1个物品中能够获得的最大价值为dp[i-1][j-weight[i]]再加上当前物品i放进去的价值value[i]。这是当前放物品能够获得的最大价值。 初始化
dp [[0]*(n1) for i in range(m)]当j0的时候表示当前背包能够载重为0此时不管选择几号物品dp[i][j]都等于0
当i0的时候表示当前只取物品0此时只有在jweight[0]的时候dp[0][j]value[0]
for j in range(weight[0], n1):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]只会放入一个物品即背包里只装一个物品 为什么在遍历重量的时候需要倒序遍历即背包重量从大到小进行遍历
假设现在背包的情况是这样的
重量价值物品0115物品1320物品2430
遍历部分的代码如下
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] 1value[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, 1515) 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]-1n很好理解就是dp数组中的元素个数weight[i]-1表示什么含义呢
因为题目中涉及到j-weight[i]这个操作因此遍历到物品i的时候我们的结束下标j一定是等于weight[i]的
在Python的循环中左闭右开为了遍历到weight[i]这个重量需要再减去1
例如当我们在遍历物品0的时候即当前的i0此时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 共计n1个数字
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(target1): # 遍历背包for num in nums: # 遍历物品if jnum:dp[j] dp[j-num]如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
爬楼梯进阶版 n,m map(int,input().split())
# 背包容量为n, 物品为m
dp [0]*(n1)
dp[0] 1for j in range(0,n1):for i in range(1,m1):# 遍历物品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、斐波那契数列 递归解法时间复杂度较高
class Solution:def fib(self, n: int) - int:if n 0:return 0elif n 1:return 1else:return self.fib(n - 1) self.fib(n - 2)动态规划解法
这里使用滚动数组的方式定义了初始化值然后进行递推由于题目已经给出了递推公式所以我们直接使用即可。
class Solution:def fib(self, n: int) - int:if n 1:return ndp0 0dp1 1for i in range(2, n 1):dpn dp0 dp1dp0 dp1dp1 dpnreturn dpn70、爬楼梯 确定dp数组及其下标含义 dp[i]爬到第i层楼梯有dp[i]种方法 确定递推公式 dp[i]可以从两个方向进行递推有两种情况可以到达该层 从dp[i-1]跨 1 步即可到达从dp[i-2]跨 2 步即可到达 所以dp[i]dp[i-1]dp[i-2]即爬到第i层的方法是爬到第i-1层的方法总数加上爬到第i-2层的方法总数之和。 dp数组如何进行初始化 题目给定了n的范围1初始化的时候只需要从1开始初始化即可 i0时dp[i]0 i1时dp[1]1表示踏上一层楼梯有一种方法即跨一步 i2时dp[2]2表示踏上二层台阶有两种方案即跨两次一步或者直接跨两步 确定遍历顺序 从前往后进行遍历 举例推导dp数组
class Solution:def climbStairs(self, n: int) - int:if n 2:return ndp0 1dp1 2for i in range(2, n):dpn dp0 dp1dp0 dp1dp1 dpnreturn dpn本题和斐波那契数列递推公式一样。 746、使用最小花费爬楼梯 确定dp数组及其下标含义 dp[i]爬到第i层的花费 确定递推公式 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]) dp数组如何进行初始化 题目中说了你可以从下标为0或者下标为1的台阶开始爬楼梯所以按照下面的进行计算 i0时dp[i]0 i1时dp[i]0 i2时dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2]) 注意本题在进行初始化的时候dp数组长度为len(cost)1因为需要跨过最顶层的台阶 确定遍历顺序 从前往后进行遍历 举例推导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、杨辉三角 思路先进行初始化将这个杨辉三角构建出来默认的初始化都为值都设置为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 res62、不同路径 动态规划
从[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] 1for 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 本题和上一题的区别就在于地图中有障碍物影响了行走但是本题只需要保证障碍物的位置处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] 1else:breakfor i in range(n):if obstacleGrid[0][i]0:dp[0][i] 1else: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、整数拆分* dp数组表示什么含义 dp[i] 表示i能拆分得到的最大乘积 dp数组递推公式 dp[i]可以由两个方向得到j*i-j) 这个的含义是i-j不进行拆分直接相乘j*dp[i-j] 这个的含义是i-j也进行拆分并用拆分后的最大值与之相乘 dp数组初始化 dp[0]和dp[1]没有实际意义 题目也说了n2dp[2] 1循环i从3开始 遍历遍历顺序 从前往后进行遍历 举例
注意代码在进行拆分的时候j是从1到i//21范围的python中for循环遍历的范围是前闭后开的所以要加上1这里可以以4为例4//22取开区间只能取到1不符合要求了。
假设正整数i拆分出来的第一个正整数为j 1ji有下面两种方案
将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开始 一直到n1开区间内存for的循环变量j从1开始 一直到i//21 j代表的是数字i可以从1开始进行拆分成j和i-j
class Solution:def integerBreak(self, n: int) - int:dp [0] * (n 1) dp[2] 1for 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[n1];dp[2] 1;for(int i3;in;i){for(int j1;j(int)i/21;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] 确定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]*(n1)dp[0] 1for i in range(1,n1):for j in range(1,i1):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/2Python中是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 Falsetarget sum_ // 2dp [0] * (target 1)# 物品nums 背包targetfor num in nums:if num target:return Falsefor j in range(target, num - 1, -1):dp[j] max(dp[j], dp[j - num] num)# print(dp)return dp[target] target01背包相对于本题主要要理解题目中物品是nums[i]重量是nums[i]价值也是nums[i]背包体积是sum//2。
本题主要判断的是背包是否能够装满target 优化版本
本题如果上面的方法时间开销较大可能存在一定的弊端因此我们可以进行优化优化的思路
将原本存数字的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 Falsetarget sum_ // 2 # 背包容量大小dp [False] * (target 1)dp[0] True for num in nums:if numtarget:return Falsefor j in range(target, num - 1, -1):dp[j] dp[j] or dp[j-num]return dp[target]1049、最后一块石头的重量II* 题目含义是尽量让石头分成重量相等的两堆相撞之后剩下的石头最小。
本题中物品重量为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 // 2dp [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则leftrighttarget其中rightsum-left可以得出left(sumtarget)/2如果sumtarget不为偶数则也没有这样的组合方式。
这里的背包容量大小是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 0if (sum_target)%21:return 0bagSize (sum_target)//2dp [0] * (bagSize1)dp[0] 1for num in nums:for j in range(bagSize,num-1,-1):dp[j]dp[j-num]return dp[bagSize]474、一和零* 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]*(m1) for _ in range(n1)]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) - zerofor 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] 1for 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 遍历顺序是什么
因为是排列问题所以先遍历背包再遍历物品注意这里需要处理numj的情况。
class Solution:def combinationSum4(self, nums: List[int], target: int) - int:dp [0] * (target 1)dp[0] 1for j in range(target 1):for num in nums:if num j:continuedp[j] dp[j - num]return dp[-1]完全背包问题之爬楼梯进阶版
完全背包问题需要先遍历背包再遍历物品。
n,m map(int,input().split())dp [0] * (n1)
dp[0] 1for i in range(n1):for j in range(1,m1):if i-j0:continuedp[i] dp[i-j]
print(dp[-1])322、零钱兑换 本题中背包为amount我们创建的dp数组的大小需要为amount1 dp数组含义是什么
dp[j]表示凑成总金额数为j所需要的最少硬币数 递推公式是什么
递推公式为dp[j] min(dp[j], dp[j-coin] 1) 如何进行初始化
当j0的时候需要的最少硬币为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] 0for j in range(amount 1):for coin in coins:if j - coin 0:continuedp[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]的值
维持不变dp[j]减去一个平方数的方案再加1即dp[j-i*i]1
dp[j] min(dp[j], dp[j-i*i]1) 如何进行初始化
因为需要求最少数量所以初始化的时候全部为float(“inf”)而dp[0] 0表示平方数和为0的方案个数有0个 遍历顺序是什么
先遍历背包再遍历物品本题中背包大小为n1物品是平方数
class Solution:def numSquares(self, n: int) - int:dp [float(inf)] * (n 1)dp[0] 0for 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同时对于示例二而言applepenapple和appleapplepen是不一样的所以属于排列问题需要先遍历背包在遍历物品。
背包长度为len(s)1物品为wordDict dp数组含义是什么
dp[i] 表示字符串长度为i的话dp[i]true表示可以拆分为一个或多个在字典中出现的单词 递推公式是什么
只有在dp[j]为True的时候并且此时s[j:i]在wordDict中dp[i]True然后直接break掉进入下一轮【只需要找到一种拆分方式即可】 如何进行初始化
全部初始化为Falsedp[0]赋值为True表示空字符串可以进行拆分 遍历顺序是什么
属于排列问题需要先遍历背包再遍历物品 class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:dp [False] * (len(s) 1)dp[0] Truefor i in range(1, len(s) 1):for j in range(i):if dp[j] and s[j:i] in wordDict:dp[i] Truebreakreturn dp[-1]198、打家劫舍 一层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: # 如果没有房屋返回0return 0prev_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 n0:return 0pre_max 0cur_max 0for num in nums:tmp cur_maxcur_max max(pre_maxnum,cur_max)pre_max tmpreturn cur_max# 1-n-1 和2-nn len(nums)if n1:return nums[0]# elif n2:# 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, val0, leftNone, rightNone):
# 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 0for 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 0for i in range(1,n):dp0 max(dp0, -prices[i])dp1 max(dp1, dp0prices[i]) # 因为dp0始终是小于dp1的所以这里使用更新后的dp0也不会有影响return dp1122、买卖股票的最佳时机II* 这道题在贪心算法章节已经使用贪心算法解决问题贪心算法的核心思想就是将差值中的正值作为利润累加起来出现负值则不作更新。
class Solution:def maxProfit(self, prices: List[int]) - int:# 贪心算法res 0for 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] 0for 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 0for i in range(1,len(prices)):dp0 max(dp0,dp1-prices[i])dp1 max(dp1,dp0prices[i]) # 因为dp0始终是小于dp1的所以这里使用更新后的dp0也不会有影响return dp1123、买卖股票的最佳时机III* 题目中说了最多可以完成两笔交易即可以只交易一次或者交易两次
同时不能同时参与多笔交易即最多手里只能有持有一次股票 dp数组含义是什么
共有五个状态尚未进行操作的状态、第一次持有股票、第一次卖出股票、第二次持有股票、第二次卖出股票
dp[i][0]-dp[i][4] 分别表示
下标含义dp[i][0]不进行操作持有的最大现金该状态不设置也可以dp[i][1]第一次持有股票拥有的最大现金dp[i][2]第一次不再持有股票拥有的最大现金dp[i][3]第二次持有股票拥有的最大现金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])
同理当j3和j4的时候的递推公式如下
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] 0dp[0][1] -prices[0]dp[0][2] 0dp[0][3] -prices[0]dp[0][4] 0for 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] 0dp[0][2] -prices[0]dp[0][3] 0for 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循环代替掉上一题的最多两次买卖也就是说上一题中最多两次买卖其实本质上也就是本题中k2
这里需要进行特殊处理的是dp[0]的值dp[0]的值有两个维度获取
前一天就持有股票继续维持状态dp[0] dp[0]前一天不持有股票需要买入股票但是手中的资金为0dp[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_dp0prices[i]# 状态4冷冻期dp[3] tmp_dp2return 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 dp1dp1 max(dp1, dp2 - prices[i], dp4 - prices[i]) #dp2 max(dp2, dp4)tmp3 dp3dp3 tmp prices[i]dp4 tmp3return max(dp2, dp3, dp4)714、买卖股票的最佳时机含手续费 本题与买卖股票的最佳时机II的区别就在于每次在进行卖出股票的时候需要一笔手续费所以只需要在交易的时候减去fee即可其余的内容不需要做任何修改。
class Solution:def maxProfit(self, prices: List[int], fee: int) - int:# 状态1今天持有股票拥有的最大现金# 状态2今天不持有股票拥有的最大现金dp1 -prices[0]dp2 0for i in range(1, len(prices)):dp1 max(dp1, dp2 - prices[i])dp2 max(dp2, dp1 prices[i] - fee)return dp2300、最长递增子序列 在回溯算法章节有一题递增子序列的题目但是的相关题目中有本题我也尝试采用回溯算法解决该题测试用例AC了但是全部测试用例超时了代码如下
class Solution:def lengthOfLIS(self, nums: List[int]) - int:res 0def backtracking(startindex, path):nonlocal resif startindex len(nums):returnif 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:continueuset.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 1for 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 res674、最长连续递增序列 这题与上一题的区别就在于要求这个序列必须在原来的数组中是连续的。连续的情况下子序列只跟前一个状态有关。如果是不连续的话状态就会跟前面的最大值有关即前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重置为1for i in range(1, len(nums)):if nums[i] nums[i - 1]:tmp 1res max(res, tmp)else:tmp 1 # 重新开始进行计算return res方法2动态规划
class Solution:def findLengthOfLCIS(self, nums: List[int]) - int:dp [1] * len(nums)res 1for i in range(1, len(nums)):if nums[i] nums[i - 1]:dp[i] dp[i - 1] 1res max(res, dp[i])return res718、最长重复子数组 本题的含义就是找出两个数组中重复部分的最大长度数组子序列的问题采用动态规划算法进行求解。本题中的子数组是要求连续的 dp数组含义是什么
dp[i][j]表示nums1数组下标1到i-1和nums2数组下标1到j-1的重复部分的最大长度必须是连续的
dp[i][j] 这里的ij需要从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]*(n21) for _ in range(n11)]遍历顺序是什么
先遍历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 0for 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] 1res 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# 遍历数组 nums1for i in range(1, len(nums1) 1):# 用于保存上一个位置的值prev 0# 遍历数组 nums2for 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 resultclass Solution:def findLength(self, nums1: List[int], nums2: List[int]) - int:res 0n1 len(nums1)n2 len(nums2)dp [0] * (n2 1)for i in range(1, n1 1):prev 0for j in range(1, n2 1):current dp[j]if nums1[i - 1] nums2[j - 1]:dp[j] prev 1res max(res, dp[j])else:dp[j] 0prev current# print(dp)return res拓展
本题我们下标统一规定了从1开始这样的目的是方便我们进行后续的递推省去了一步初始化的步骤。如果需要从0开始就需要对第一行和第一列进行特殊的初始化这样比较麻烦。相等的地方需要赋值为1。
114、最长公共子序列* 本题与上一题最长重复子数组的区别就在于这里不需要连续只需要是相对连续的即可 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] 1else: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]*(t21)for i in range(1,t11):prev 0for j in range(1,t21):current dp[j]# print(current)if text1[i-1]text2[j-1]:dp[j] prev 1 # 01 保留上一行的值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] 1else: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 0for num in nums:tmp numres max(res, tmp)if tmp 0:tmp 0return 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]*ndp[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 Falses_ t_ 0while s_ len(s) and t_ len(t):if s[s_] t[t_]:s_ 1t_ 1return s_ len(s)解法二动态规划
本题中只需要考虑删除元素的情况不需要考虑添加元素的情况因此还是比较简单的 【编辑距离的入门题目】
只需要判断二者的公共子序列长度是否为s的长度即可 dp数组含义是什么
dp[i][j]表示以下标为i-1为结尾的字符串s和以下标为j-1结尾的字符串t相同子序列的长度 递推公式是什么
分为两种情况 s[i-1]t[j-1] 即t中找到了一个字符在s中出现了 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] 1else:dp[i][j] dp[i][j - 1]return n1 dp[-1][-1] # 即公共子序列的长度为s的长度n1115、不同的子序列(**) [外链图片转存中…(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]的值 例如sbaggtbag再进行判断的时候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数组
但是在j0的时候即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”tbag为例推导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] 1for 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] ifor 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] 1else: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(n11):dp[i][0] ifor j in range(n21):dp[0][j] jfor 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]相等则分成三种情况讨论
ij单个字符是回文子串j-i1即j和i相差1个字符也是回文子串j-i≥1相差多个字符就需要看中间的字符是否也是回文子串即dp[i1][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 0dp [[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 1dp[i][j] Trueelse:if dp[i 1][j - 1]:res 1dp[i][j] True# print(dp[i])return res简化版本
class Solution:def countSubstrings(self, s: str) - int:n len(s)res 0dp [[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] and (j - i 1 or dp[i 1][j - 1]):res 1dp[i][j] Truereturn res5、最长回文子串(*)
[外链图片转存中…(img-5qpifOPz-1712798807548)]
本题只需要在上一题遍历的过程中进行长度的判断即可
初始化dp数组全部为False即可
递推的顺序依旧是从左下角到左上角
class Solution:def longestPalindrome(self, s: str) - str:n len(s)res 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]:# length1if j - i 1:dp[i][j] Trueif len(res) j - i 1:res s[i : j 1]else:if dp[i 1][j - 1]:dp[i][j] Trueif len(res) j - i 1:res s[i : j 1]return res简化版本
class Solution:def longestPalindrome(self, s: str) - str:n len(s)ans 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] and (j - i 1 or dp[i 1][j - 1]):if len(ans) j - i 1:ans s[i : j 1]dp[i][j] Truereturn ans[外链图片转存中…(img-EX155S77-1712798807550)]
516、最长回文子序列(**) 本题的子序列和子串的区别就在于子序列可以是原本的字符删除其中一部分得到的一个序列子串必须是连续的。
本题求的是最长子序列的长度区别于【5、最长回文子串】求最长的子串和【647、回文子串】求数量 dp数组含义是什么
dp[i][j]表示字符串s在[i,j]范围内最长的回文子序列的长度为dp[i][j] 递推公式是什么
如果s[i]和s[j]相等则dp[i][j] dp[i1][j-1] 2 如果s[i]和s[j]不相等可以分成两种情况
加入s[i]的回文子序列的长度为dp[i][j-1]加入s[j]的回文子序列的长度为dp[i1][j]
则可以判断二者其中的一个加入到子序列中的时候能够得到的最大值也就是dp[i][j] max(dp[i][j-1], dp[i1][j]) 如何进行初始化
对角线部分初始化为1因为对角线已经初始化过了所以j的遍历顺序需要从i1开始 遍历顺序是什么
从左下到右上方i从len(s)到0j从i1到len(s)不从i开始的原因是因为对角线部分即ij的时候我们已经初始化过了这一点也是本题与前两题不同之处。 最终的结果取第一行的最后一个数字即右上角的数字
class Solution:def longestPalindromeSubseq(self, s: str) - int:n len(s)dp [[0] * n for _ in range(n)]for i in range(n):dp[i][i] 1for i in range(n - 1, -1, -1):for j in range(i 1, n):if s[i] s[j]:dp[i][j] dp[i 1][j - 1] 2else:dp[i][j] max(dp[i 1][j], dp[i][j - 1])return dp[0][-1]总结
模板 dp数组含义是什么 递推公式是什么 如何进行初始化 遍历顺序是什么 举例说明
01背包问题总结
完全背包问题总结
股票问题总结
动态规划121.买卖股票的最佳时机动态规划122.买卖股票的最佳时机II动态规划123.买卖股票的最佳时机III动态规划188.买卖股票的最佳时机IV动态规划309.最佳买卖股票时机含冷冻期动态规划714.买卖股票的最佳时机含手续费
第一题股票只能买卖一次求最大利润
第二题股票可以买卖多次求最大利润
第三题最多只能买卖两次求最大利润
第四题最多能够买卖k次求最大利润这题是上一题的扩展版本总结出规律即可状态j为奇数时卖出股票为偶数时为卖出股票
第五题冷冻期导致问题多出了两个状态一个是冷冻期一个是不持有股票的状态今天卖出股票和前2天卖出股票区别于冷冻期
第六题本质上是第二题只是多了一笔手续费只需要在卖出股票的递推公式中减去fee即可其余代码不需要改动
子序列问题总结
最长上升子序列最长连续递增子序列最长重复子数组最长公共子序列不相交的线最大子序和
直接将dp数组定义为题目所需要进行求解的即可
在进行动态规划递推的时候通常需要分为以下两种情况
s1[i-1]s2[j-1]s1[i-1]!s2[j-1]
编辑距离问题总结
判断子序列不同的子序列两个字符串的删除操作编辑距离
首先dp[i][j]所表达的含义一定是字符串s1从0到i-1和字符串s2从0到j-1位置的字符串的子序列长度/最小操作次数
在进行动态规划递推的时候通常需要分为以下两种情况
s1[i-1]s2[j-1]s1[i-1]!s2[j-1]
这里需要格外的注意s2不要写成s1了已经误写了好几次了
参考资料
