做货代在哪个网站找客源,永久免费的网站,网站推广包年,设计必备网站算法总结4 动态规划一、动态规划1.1、基础问题11.1.1、509. 斐波那契数列1.1.2、70. 爬楼梯1.1.3、746. 使用最小花费爬楼梯1.2、基础问题21.2.1、62. 不同路径1.2.2、63. 不同路径Ⅱ1.2.3、343. 整数拆分1.2.4、96. 不同的二叉搜索树1.3、背包问题1.3.1、01背包1.3.1.1、单次选…
算法总结4 动态规划一、动态规划1.1、基础问题11.1.1、509. 斐波那契数列1.1.2、70. 爬楼梯1.1.3、746. 使用最小花费爬楼梯1.2、基础问题21.2.1、62. 不同路径1.2.2、63. 不同路径Ⅱ1.2.3、343. 整数拆分1.2.4、96. 不同的二叉搜索树1.3、背包问题1.3.1、01背包1.3.1.1、单次选择最大价值1.3.1.2、单次选择最大重量416. 分割等和子集1049. 最后一块石头的重量 II474. 一和零双维度背包1.3.1.3、单次选择装满可能性总数494. 目标和1.3.2、完全背包1.3.2.1、重复选择最大价值1.3.2.2、重复选择组合装满可能性总数518. 零钱兑换 II组合问题1.3.2.3、重复选择排列装满可能性总数377. 组合总和 Ⅳ70. 爬楼梯139. 单词拆分1.3.2.4、重复选择 装满的最少数量322. 零钱兑换279. 完全平方数1.3.3、多重背包参考1.4、打家劫舍1.4.1、198. 打家劫舍1.4.2、213. 打家劫舍 II1.4.3、337.打家劫舍 III1.5、股票问题1.5.1、121. 买卖股票的最佳时机 - 只能买卖一次1.5.2、122. 买卖股票的最佳时机 II - 能买卖多次1.5.3、123. 买卖股票的最佳时机 III1.5.4、188. 买卖股票的最佳时机 IV1.5.5、309. 最佳买卖股票时机含冷冻期1.5.6、714. 买卖股票的最佳时机含手续费1.5、子序列问题1.5.1、子序列不连续1.5.1.1、300. 最长上升子序列1.5.1.2、1143. 最长公共子序列1.5.1.3、1035. 不相交的线1.5.2、子序列连续1.5.2.1、674. 最长连续递增序列1.5.2.2、718. 最长重复子数组1.5.2.3、53. 最大子序和1.5.3、编辑距离1.5.3.1、392. 判断子序列1.5.3.2、115. 不同的子序列1.5.3.3、583. 两个字符串的删除操作1.5.3.4、72. 编辑距离1.5.4、回文1.5.4.1、647. 回文子串1.5.4.2、最长回文子串1.5.4.3、516. 最长回文子序列一、动态规划
动态规划英文Dynamic Programming简称DP如果某一问题有很多重叠子问题使用动态规划是最有效的。
动态规划中每一个状态一定是由上一个状态推导出来的。而贪心算法不同贪心没有状态推导而是从局部直接选最优的。
动态规划问题将被拆解为如下五步
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 1.1、基础问题1
1.1.1、509. 斐波那契数列
力扣题目链接
F(0) 0F(1) 1 F(n) F(n - 1) F(n - 2)其中 n 1
1一般解法递归
class Solution:def fib(self, n: int) - int:if n 2:return nelse:return self.fib(n-1) self.fib(n-2)时间复杂度O(2^n) 空间复杂度O(n)
2高级解法动态规划
确定dp数组dp table以及下标的含义 dp[i]的含义是第i个数的斐波那契数值是dp[i]确定递推公式 题目已经给我们了状态转移方程F(n) F(n - 1) F(n - 2)其中 n 1dp数组如何初始化 题目也直接给了我们F(0) 0F(1) 1确定遍历顺序 从递归公式dp[i] dp[i - 1] dp[i - 2];中可以看出dp[i]是依赖 dp[i - 1] 和 dp[i - 2]那么遍历的顺序一定是从前到后遍历的举例推导dp数组 按照这个递推公式dp[i] dp[i - 1] dp[i - 2]我们来推导一下当N为10的时候dp数组应该是如下的数列
0 1 1 2 3 5 8 13 21 34 55如果代码写出来发现结果不对就把dp数组打印出来看看和我们推导的数列是不是一致的。
综上代码如下
class Solution:def fib(self, n: int) - int:if n 2:return ndp [0]*(n1)dp[0] 0dp[1] 1for i in range(2, n1):dp[i] dp[i-1]dp[i-2]return dp[n]时间复杂度O(n) 空间复杂度O(n)
上面我们维护了一个长度为N1的数组实际上我们只需要维护两个数值就行因为我们只需要最后一个数。修改数组为两个数值
class Solution:def fib(self, n: int) - int:if n 2:return ndp1, p2 0, 1for i in range(2, n1):dp1, dp2 dp2, dp1dp2return dp2时间复杂度O(n) 空间复杂度O(1) 1.1.2、70. 爬楼梯
力扣题目链接
1一般解法递归超时
class Solution:def climbStairs(self, n: int) - int:if n2:return nelse:return self.climbStairs(n-1) self.climbStairs(n-2)2高级解法动态规划
确定dp数组dp table以及下标的含义 dp[i]的含义是上第i个阶梯的步数为dp[i]确定递推公式 因为一次走一步或两步dp[i-1]往上走一个台阶为dp[i]dp[i-2]往上走两个台阶为dp[i]那么dp[i] dp[i-1]dp[i-2]dp数组如何初始化 这里比较有争议的点是dp[0]是0还是1。按照公式递推dp[0]应该是1但是按照实际场景0阶台阶走的步数应该是0。 这里直接说明不考虑dp[0]。如果初始化只初始化dp[1] 1dp[2] 2然后从i 3开始递推这样才符合dp[i]的定义。确定遍历顺序 从递归公式dp[i] dp[i - 1] dp[i - 2];中可以看出dp[i]是依赖 dp[i - 1] 和 dp[i - 2]那么遍历的顺序一定是从前到后遍历的举例推导dp数组 举例当n为5的时候dp tabledp数组应该是这样的 可以看出这就是上一题的斐波那契数列唯一的区别是没有讨论dp[0]应该是什么因为dp[0]在本题没有意义。
根据规则代码如下
class Solution:def climbStairs(self, n: int) - int:# n为1 和 2if n3:return n# 初始化# 一阶楼梯dp1 1# 二阶楼梯dp2 2# 递归公式for i in range(3, n1):dp1, dp2 dp2, dp1dp2return dp21.1.3、746. 使用最小花费爬楼梯
力扣题目链接
高级解法动态规划
确定dp数组以及下标的含义: 动态规划需要有一个数组来记录状态这里只用一个一维数组dp[i]就可以了。 dp[i]的定义到达第i个台阶所花费的最少体力为dp[i]。确定递推公式: 因为一次走一步或者两步那么可以有两个途径得到dp[i]一个是dp[i-1] 一个是dp[i-2]。 因为是求花费的体力最小那么一定是选最小的所以dp[i] min(dp[i - 1], dp[i - 2]) cost[i]这个意思是选取前一步或者两步的最小值加上走到当前台阶的体力等于从头开始走到当前的总体力花费。dp数组如何初始化 同理题目中由台阶0或1开始那么初始化dp[0] 和dp[1]就够了后面的由公式递推。
dp0, dp1 cost[0], cost[1]确定遍历顺序 因为是模拟台阶而且dp[i]又dp[i-1]dp[i-2]推出所以是从前到后遍历cost数组就可以了。 举例推导dp数组 拿示例2cost [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 来模拟一下dp数组的状态变化如下
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:n len(cost)dp [0]*(n)dp[0] cost[0]dp[1] cost[1]for i in range(2,n):dp[i] min(dp[i-1], dp[i-2]) cost[i]return min(dp[n-1], dp[n-2])时间复杂度O(n) 空间复杂度O(n)
这里同样可以只维持两个值就行了从而使代码 时间复杂度O(n) 空间复杂度O(1)
但为了直观平时还是建议上述第一种写法。 1.2、基础问题2
1.2.1、62. 不同路径
力扣题目链接
1.一般解法广度深度优先搜索递归超时 可以转化为求二叉树叶子节点的个数
class Solution:def uniquePaths(self, m: int, n: int) - int:def dfs(i, j, m, n):# 越界if im or jn:return 0# 找到一种方法if im and jn:return 1# 递归类似于走楼梯而这里是往右或者往下走return dfs(i1, j, m, n) dfs(i, j1, m, n)return dfs(1, 1, m, n)2.动态规划 确定dp数组dp table以及下标的含义 dp[i][j] 表示从(0, 0)出发到(i, j) 有dp[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[i][j]只有这两个方向过来。 dp数组的初始化 如何初始化呢首先dp[i][0]一定都是1因为从(0, 0)的位置到(i, 0)的路径只有一条那么dp[0][j]也同理。
所以初始化代码为
for i in range(m):dp[i][0] 0
for i in range(n):dp[0][j] 0确定遍历顺序 这里要看一下递归公式dp[i][j] dp[i - 1][j] dp[i][j - 1]dp[i][j]都是从其上方和左方推导而来那么从左到右一层一层遍历就可以了。 这样就可以保证推导dp[i][j]的时候dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。 举例推导dp数组 如图所示 综上代码如下
class Solution:def uniquePaths(self, m: int, n: int) - int:# 二维数组dp [[1]*n for _ in range(m)]# 数组赋值for i in range(1, m):for j in range(1, n):dp[i][j] dp[i-1][j] dp[i][j-1]return dp[m-1][n-1]时间复杂度O(m × n) 空间复杂度O(m × n)
同样的在理解上述方法中表格的值的规律的情况下可以只用维护一个一维数组来减少空间复杂度下一行等于上一行的与前一个点的和。
class Solution:def uniquePaths(self, m: int, n: int) - int:dp [1]*nfor i in range(1, m):for j in range(1, n):dp[j] dp[j-1]return dp[n-1]时间复杂度O(m × n) 空间复杂度O(n)
一般这第二种同样也可能不便于理解使用第一种方法即可。 1.2.2、63. 不同路径Ⅱ
力扣题目链接
动态规划 动规五部曲
确定dp数组dp table以及下标的含义 dp[i][j] 表示从(0, 0)出发到(i, j) 有dp[i][j]条不同的路径。 这个同前面的题的含义确定递推公式 递推公式和 62.不同路径 一样为dp[i][j] dp[i - 1][j] dp[i][j - 1]。 但这里需要注意一点因为有了障碍(i, j)如果就是障碍的话应该就保持初始状态初始状态为0。
所以需要加入条件判断
# 当(i, j)没有障碍的时候再推导dp[i][j]
if obstacleGrid[i][j] 0:dp[i][j] dp[i - 1][j] dp[i][j - 1]# 或者
if obstacleGrid[i][j] 1:continue
dp[i][j] dp[i - 1][j] dp[i][j - 1];dp数组如何初始化 在 62.不同路径 不同路径中我们给出如下的初始化
dp [[0]*n for _ in range(m)]
for i in range(m):dp[0][i] 1
for j in range(n):dp[j][0] 1虽然是初始化是dp [[1]*n for _ in range(m)]但这是简写但实际上为上面的过程。但这道题如上图如果(i, 0) 这条边有了障碍之后障碍之后包括障碍都是走不到的位置了所以障碍之后的dp[i][0]应该还是初始值0。正确的初始化如下
dp [[0]*n for _ in range(m)]
for i in range(m):if obstacleGrid[0][i] 1:breakdp[0][i] 1
for j in range(n):if obstacleGrid[j][0] 1:breakdp[j][0] 1注意代码里for循环的终止条件一旦遇到obstacleGrid[i][0] 1的情况就停止dp[i][0]的赋值1的操作dp[0][j]同理。
确定遍历顺序 从递归公式dp[i][j] dp[i - 1][j] dp[i][j - 1] 中可以看出一定是从左到右一层一层遍历这样保证推导dp[i][j]的时候dp[i - 1][j] 和 dp[i][j - 1]一定是有数值。
for i in range(1, m):for j in range(1, n):if obstacleGrid[i][j] 1:continuedp[i][j] dp[i-1][j] dp[i][j-1]举例推导dp数组 拿示例1来举例如题 对应的dp table 如图 综上所述
class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int:length len(obstacleGrid)width len(obstacleGrid[0])# 如果障碍物在起点或终点直接返回0if obstacleGrid[0][0] 1 or obstacleGrid[length-1][width-1]1:return 0# 创建一个dp tabledp [[0]*width for _ in range(length)]# 两个循环初始化 dp tablefor i in range(length):# 遇到障碍物后续都为0if obstacleGrid[i][0] 1:breakdp[i][0] 1for j in range(width):# 遇到障碍物后续都为0if obstacleGrid[0][j] 1:breakdp[0][j] 1# 填表for i in range(1, length):for j in range(1, width):if obstacleGrid[i][j] 1:continuedp[i][j] dp[i-1][j] dp[i][j-1]return dp[length-1][width-1]时间复杂度O(n × m)n、m 分别为obstacleGrid 长度和宽度 空间复杂度O(n × m)
class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int:length len(obstacleGrid)width len(obstacleGrid[0])# 如果障碍物在起点或终点直接返回0if obstacleGrid[0][0] 1 or obstacleGrid[length-1][width-1]1:return 0# 创建一个dp tabledp [0]*width# 一个循环先从obstacleGrid第一行开始for i in range(width):# 遇到障碍物后续都为0if obstacleGrid[0][i] 1:breakdp[i] 1# 填表# 从第二行开始for i in range(1, length):# 这里不能从1开始因为可能位置0有障碍物所以从第0列开始for j in range(width):# 有障碍物走法数量直接为0if obstacleGrid[i][j] 1:dp[j] 0# 这里不能直接else否则会用下面公式累加而改变第一列的值elif j!0:dp[j] dp[j-1]return dp[width-1]时间复杂度O(n × m)n、m 分别为obstacleGrid 长度和宽度 空间复杂度O(m)
本题是 62.不同路径 的障碍版整体思路大体一致。但就算是做过 62.不同路径在做本题也会有感觉遇到障碍无从下手。其实只要考虑到遇到障碍dp[i][j]保持0就可以了。也有一些小细节例如初始化的部分很容易忽略了障碍之后应该都是0的情况。 1.2.3、343. 整数拆分
力扣题目链接
1 动态规划 这道题求整数拆分后的最大乘积值的组合使用动态规划来解大的整数的拆分最大组合乘积等于其子整数的拆分最大组合乘积的乘积。
确定dp数组dp table以及下标的含义 dp[i]拆分数字i可以得到的最大乘积为dp[i]。确定递推公式 递推公式dp[i] max(dp[i], max((i - j) * j, dp[i - j] * j)); j * (i - j) 是单纯的把整数拆分为两个数相乘而j * dp[i - j]是拆分成两个以及两个以上的个数相乘加上dp[i]是跟上一次拆分组合比每次保留最大值。dp的初始化 有的题解里会给出dp[0] 1dp[1] 1的初始化但解释比较牵强主要还是因为这么初始化可以把题目过了。严格从dp[i]的定义来说dp[0] dp[1] 就不应该初始化也就是没有意义的数值。 拆分0和拆分1的最大乘积是多少这是无解的。 这里只初始化dp[2] 1从dp[i]的定义来说拆分数字2得到的最大乘积是1。dp[i] 是依靠 dp[i - j]的状态所以遍历i一定是从前向后遍历先有dp[i - j]再有dp[i]。 枚举j的时候是从1开始的。i是从3开始这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。
所以遍历顺序为
for i in range(3, n1):for j in range(1, i//21):dp[i] max(dp[i], max(j*(i-j), j*dp[i-j]))举例推导dp数组 举例当n为10 的时候dp数组里的数值如下
class Solution:def integerBreak(self, n: int) - int:# 数值加上一索引才会到ndp [0]*(n1)# 初始化从2开始因为k2dp[2] 1# 拆分成kk2,2前面已经初始化从3开始for i in range(3, n1):# 拆分成j 和 i-j 例如1*(3-1) 2*(3-2)所以整除以一半再加上一。for j in range(1, i//21):# 遍历j时更新dp[i]的最大值# 这里j*(i-j)是将i拆分成两部分j*dp[i-j]是将i拆分成两部分以上dp[i] max(dp[i], max(j*(i-j), j*dp[i-j]))# dp中最后一个索引为n即将n拆分的最大乘积return dp[-1]时间复杂度O(n^2) 空间复杂度O(n)
2 数学证明 本题也可以用贪心每次拆成n个3如果剩下是4则保留4然后相乘但是这个结论需要数学证明其合理性可以自行查阅研究。
class Solution:def integerBreak(self, n: int) - int:if n2:return 1if n3:return 2if n4:return 4result 1while n4:result * 3n - 3result * nreturn result1.2.4、96. 不同的二叉搜索树
力扣题目链接
动态规划
确定dp数组dp table以及下标的含义 dp[i] i个节点组成的二叉搜索树的个数为dp[i]。确定递推公式 在上面的分析中其实已经看出其递推关系 dp[i] dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] j相当于是头结点的元素从1遍历到i为止。 所以递推公式dp[i] dp[j - 1] * dp[i - j]; j-1 为j为头结点左子树节点数量i-j 为以j为头结点右子树节点数量dp数组如何初始化 初始化只需要初始化dp[0]就可以了推导的基础都是dp[0]。 那么dp[0]应该是多少呢 从定义上来讲空节点也是一棵二叉树也是一棵二叉搜索树这是可以说得通的。 从递归公式上来讲dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0也需要dp[以j为头结点左子树节点数量] 1 否则乘法的结果就都变成0了。 所以初始化dp[0] 1确定遍历顺序 首先一定是遍历节点数从递归公式dp[i] dp[j - 1] * dp[i - j]可以看出节点数为i的状态是依靠 i之前节点数的状态。 那么遍历i里面每一个数作为头结点的状态用j来遍历。
for i in range(1, n1):for j in range(1, i1):dp[i] dp[j-1]*dp[i-j]举例推导dp数组 n为5时候的dp数组状态如图 综上代码如下
class Solution:def numTrees(self, n: int) - int:# 从0到ndp [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[-1]时间复杂度O(n2)O(n^2)O(n2) 空间复杂度O(n)O(n)O(n) 1.3、背包问题 背包问题简单来说就是将单次、无限重复或者有限重复数量的物品通过满足一定的题目需求而放入有限大小的背包中。
而根据物品的三种不同规则我们将分为三种背包问题01背包完全背包和多重背包。
它们的总结如下图 但我们可以看到还有其他类型的背包在其中但对于面试的话其实掌握01背包和完全背包就够用了最多可以再来一个多重背包。
至于其他的背包问题面试几乎不会问都是竞赛级别的了leetcode上连多重背包的题目都没有所以题库也告诉我们01背包和完全背包就够用了。但如果你热爱学习喜欢钻研则一本背包问题的经典书籍送给你 背包问题九讲 2.0。
理解背包问题01背包非常基础和重要因为其他问题基本由此为基础衍生而来。我们先从纯背包问题开始去理解和学习再去延伸和转化到leetcode题目。 1.3.1、01背包
一次数量的物品根据要求放入背包中。
暴力解法 每一件物品其实只有两个状态取或者不取所以可以使用回溯法搜索出所有的情况那么时间复杂度就是o(2n)o(2^n)o(2n)这里的n表示物品数量。
所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化 1.3.1.1、单次选择最大价值
问题描述 有nnn件物品和一个最多能背重量为www的背包。第iii件物品的重量是weight[i]weight[i]weight[i]得到的价值是value[i]value[i]value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
简单例子 有w4w4w4重量的背包 有n3n3n3件物品表示如下
重量 weight[i]价值 value[i]物品0115物品1320物品2430
问背包能背的物品的最大价值是多少
(1). 二维DP数组
动态规划五部曲 确定dp数组以及下标的含义 对于背包问题有一种写法 是使用二维数组即dp[i][j]dp[i][j]dp[i][j] 表示从下标为[0−i][0-i][0−i]的物品里任意取放进容量为j的背包价值总和最大是多少。 确定递归公式 dp[i][j]dp[i][j]dp[i][j]的含义为从下标为0−i0-i0−i的物品里任取放进容量为j的背包价值总和最大是多少。 从两个方向可以推出dp[i][j]dp[i][j]dp[i][j]: 不放物品i 当物品i的重量大于背包j的重量时(即把背包清空也装不下)物品i无法放进背包中所以被背包内的价值依然和前面相同里面不放物品i的最大价值此时dp[i][j]dp[i][j]dp[i][j]就是dp[i−1][j]dp[i - 1][j]dp[i−1][j]放物品i 想要放入一个物品要此刻dp[i][j]dp[i][j]dp[i][j]的背包腾出物品i以及weight[i]weight[i]weight[i]的重量于是腾出后的价值为dp[i−1][j−weight[i]]dp[i-1][j-weight[i]]dp[i−1][j−weight[i]]i−1i-1i−1则为腾出i之后前面000 - i−1i-1i−1的物品j−weight[i]j-weight[i]j−weight[i]为腾出weight[i]weight[i]weight[i]的重量。放入weight[i]weight[i]weight[i]重量的物品后的总价值为dp[i−1][j−weight[i]]value[i]dp[i-1][j-weight[i]]value[i]dp[i−1][j−weight[i]]value[i]。 数组的初始化 首先从dp[i][j]dp[i][j]dp[i][j]的定义出发如果背包容量jjj为000的话即dp[i][0]dp[i][0]dp[i][0]无论是选取哪些物品背包价值总和一定为000。如图 再看其他情况状态转移方程 dp[i][j]max(dp[i−1][j],dp[i−1][j−weight[i]]value[i])dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]]value[i])dp[i][j]max(dp[i−1][j],dp[i−1][j−weight[i]]value[i])因为iii是由i−1i-1i−1推导而来所以i0i0i0一定要初始化。 即初始化dp[0][j]dp[0][j]dp[0][j]存放编号为0的物品时各个容量的背包所能存放的最大值。 于是 当weight[0]jweight[0]jweight[0]j说明当前背包的容量装不下第0个物品那么dp[0][j]0dp[0][j]0dp[0][j]0当weight[0]jweight[0]jweight[0]j说明当前的背包的重量能够装下第0个物品那么dp[0][j]value[0]dp[0][j]value[0]dp[0][j]value[0]
for j in range(bagweight):if jweight[0]:dp[0][j]value[0]else:dp[0][j]0至于其他值都会被递推公式推出结果直接初始化微为即可初始化完成后为 4. 确定遍历顺序 有两个遍历的维度物品与背包重量。 先遍历 物品还是先遍历背包重量呢两者皆可但是先遍历物品更好理解比较贴合上面的图。
# 物品的编号
for i in range(1, len(weight)):# 包的大小for j in range(1, bagweight):# 大于包的大小不放与上一个物品价值相等if jweight[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])举例推导dp数组 最终结果就是dp[2][4]dp[2][4]dp[2][4]
整体代码二维
def bagpack_problem1(bag_size, weight, value) - int: # rows 物品 cols 背包rows, cols len(weight), bag_size 1# 这里先遍历物品再遍历背包。# 若先遍历背包再遍历物品下面dp表的创建行列要互换初始化互换下面的两个循环也要互换dp [[0 for _ in range(cols)] for _ in range(rows)]# 初始化dp数组# 第0列0-rows行因为背包大小为0则直接为0for i in range(rows): dp[i][0] 0first_item_weight, first_item_value weight[0], value[0]# 第0行1-rows列(因为0在前面已经赋值为0了所以从1开始)小于等于背包大小的物品赋予物品大小的值其余为0for j in range(1, cols): if first_item_weight j: dp[0][j] first_item_value# 更新dp数组: 先遍历物品, 再遍历背包. for i in range(1, len(weight)): cur_weight, cur_val weight[i], value[i]# 注意这里能写成for j in range(nums[i],target1)这样吗# 不行因为前面的值需要if cur_weight j 去将0填空便于下一行的值的依赖# 所以这里不同于二维数组不需要依赖而直接到nums[i]为止for j in range(1, cols): if cur_weight j: # 说明背包装不下当前物品. dp[i][j] dp[i - 1][j] # 所以不装当前物品. else: # 定义dp数组: dp[i][j] 前i个物品里放进容量为j的背包价值总和最大是多少。dp[i][j] max(dp[i - 1][j], dp[i - 1][j - cur_weight] cur_val)print(dp)if __name__ __main__: bag_size 4weight [1, 3, 4]value [15, 20, 30]bagpack_problem1(bag_size, weight, value)(2). 一维DP数组滚动数组
背包问题的状态其实都是可以压缩的。
在使用二维数组的时候递推公式dp[i][j]max(dp[i−1][j],dp[i−1][j−weight[i]]value[i])dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i])dp[i][j]max(dp[i−1][j],dp[i−1][j−weight[i]]value[i])
如果把dp[i−1]dp[i - 1]dp[i−1]那一层拷贝到dp[i]dp[i]dp[i]上表达式完全可以是dp[i][j]max(dp[i][j],dp[i][j−weight[i]]value[i])dp[i][j] max(dp[i][j], dp[i][j - weight[i]] value[i])dp[i][j]max(dp[i][j],dp[i][j−weight[i]]value[i])
与其把dp[i−1]dp[i - 1]dp[i−1]这一层拷贝到dp[i]dp[i]dp[i]上不如只用一个一维数组了只用dp[j]dp[j]dp[j]一维数组也可以理解是一个滚动数组。
这就是滚动数组的由来需要满足的条件是上一层可以重复利用直接拷贝到当前层。
动态规划五部曲
确定dpdpdp数组的定义 在一维dpdpdp数组中dp[j]dp[j]dp[j]表示容量为jjj的背包所背的物品价值可以最大为dp[j]dp[j]dp[j]。一维dpdpdp数组的递推公式 dp[j]dp[j]dp[j]为 容量为jjj的背包所背的最大价值那么如何推导dp[j]dp[j]dp[j]呢 dp[j]dp[j]dp[j]可以通过dp[j−weight[i]]dp[j - weight[i]]dp[j−weight[i]]推导出来dp[j−weight[i]]dp[j - weight[i]]dp[j−weight[i]]表示容量为j−weight[i]j - weight[i]j−weight[i]的背包所背的最大价值。 dp[j−weight[i]]value[i]dp[j - weight[i]] value[i]dp[j−weight[i]]value[i] 表示 容量为 jjj - 物品iii重量 的背包 加上 物品iii的价值。也就是容量为jjj的背包放入物品iii了之后的最大总价值即dp[j]dp[j]dp[j] 此时dp[j]dp[j]dp[j]有两个选择一个是取自己dp[j]dp[j]dp[j] 相当于 二维dp数组中的dp[i−1][j]dp[i-1][j]dp[i−1][j]即不放物品iii一个是取dp[j−weight[i]]value[i]dp[j - weight[i]] value[i]dp[j−weight[i]]value[i]即放物品iii指定是取最大的因为是求最大价值所以递推公式为:
dp[j] max(dp[j], dp[j - weight[i]] value[i]);一维dp数组如何初始化 那么dp数组除了下标0的位置初始为0其他下标应该初始化多少呢 看一下递归公式dp[j] max(dp[j], dp[j - weight[i]] value[i]); dp数组在推导的时候一定是取价值最大的数如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。 这样才能让dp数组在递归公式的过程中取的最大的价值而不是被初始值覆盖了。 那么我假设物品价值都是大于0的所以dp数组初始化的时候都初始为0就可以了。一维dp数组遍历顺序
for i in range(len(weight)):for j in reversed(range(weight[i], bagweight1)):dp[j] max(dp[j], dp[j-weight[i]]value[i])这里大家发现和二维dp的写法中遍历背包的顺序是不一样的 二维dp遍历的时候背包容量是从小到大而一维dp遍历的时候背包是从大到小。 为什么呢 倒序遍历是为了保证物品i只被放入一次。但如果一旦正序遍历了那么物品0就会被重复加入多次 举一个例子物品0的重量weight[0] 1价值value[0] 15 如果正序遍历 dp[1] dp[1 - weight[0]] value[0] 15 dp[2] dp[2 - weight[0]] value[0] 30 此时dp[2]就已经是30了意味着物品0被放入了两次所以不能正序遍历。 为什么倒序遍历就可以保证物品只放入一次呢 倒序就是先算dp[2] dp[2] dp[2 - weight[0]] value[0] 15 dp数组已经都初始化为0 dp[1] dp[1 - weight[0]] value[0] 15 所以从后往前循环每次取得状态不会和之前取得状态重合这样每种物品就只取一次了。 那么问题又来了为什么二维dp数组历的时候不用倒序呢 因为对于二维dpdp[i][j]都是通过上一层即dp[i - 1][j]计算而来本层的dp[i][j]并不会被覆盖 再来看看两个嵌套for循环的顺序代码中是先遍历物品嵌套遍历背包容量那可不可以先遍历背包容量嵌套遍历物品呢不可以 因为一维dp的写法背包容量一定是要倒序遍历原因上面已经讲了如果遍历背包容量放在上一层那么每个dp[j]就只会放入一个物品即背包里只放入了一个物品。 倒序遍历的原因是本质上还是一个对二维数组的遍历并且右下角的值依赖上一层左上角的值因此需要保证左边的值仍然是上一层的从右向左覆盖。 这里如果读不懂就再回想一下dp[j]的定义或者就把两个for循环顺序颠倒一下试试 所以一维dp数组的背包在遍历顺序上和二维其实是有很大差异的这一点大家一定要注意。
举例推导dp数组 一维dp分别用物品0物品1物品2 来遍历背包最终得到结果如下
整体代码一维
def bag_problem():weight [1, 3, 4]value [15, 20, 30]bag_weight 4# 初始化: 全为0dp [0] * (bag_weight 1)# 先遍历物品, 再遍历背包容量for i in range(len(weight)):for j in range(bag_weight, weight[i] - 1, -1):# 递归公式dp[j] max(dp[j], dp[j - weight[i]] value[i])print(dp)bag_problem()总结 动态规划问题枚举的顺序只有一个原则如果b状态的计算依赖于a状态那么a状态必须在b状态之前被枚举和计算。
二维数组时物品和背包的顺序从小到大遍历二者可以内外互换物品顺序可颠倒但初始化操作也要相应颠倒而背包只可逆序因为背包的结果与前面一次较小的背包结果有关而前面的结果是上一层的拷贝而不会受到这一层更新的干扰而重复累加避免重复计算重复计算会变成完全背包。
对于二维dpdp[i][j]都是通过上一层即dp[i - 1][j]计算而来所以二维无需逆序遍历当然背包也可以逆序不影响结果。
01背包最大重量/价值二维一维初始化第0行0列初始化无需初始化内外循序物品背包 | 背包物品物品背包物品顺序正序|逆序正序|逆序背包顺序正序|逆序逆序递推公式dp[i][j]max(dp[i-1]j[j], dp[i-1][j-weight[i]]value[i])dp[j]max(dp[j], dp[j-weight[i]]value[i])1.3.1.2、单次选择最大重量
问题描述 有nnn件物品和一个最多能背重量为www的背包。第i件物品的重量是weight[i]weight[i]weight[i]每件物品只能用一次求解将哪些物品装入背包里物品重量总和最大。
分析 这个问题没有给每个物品的价值也没有问最多能获得多少价值而是问最多能装多满。 实际上在这里如果我们把每个物品的大小当作每个物品的价值就可以完美解决这个问题。
简单例子 有w4w4w4重量的背包 有n3n3n3件物品表示如下 这里增设一列不存在的价值值与重量相等模拟等于上一题求最大价值。
重量 weight[i]价值 value[i]物品011物品133物品244
问背包能背的物品的最大价值(或者重量)是多少
代码同上只不过values与weights相等那么只需把values改成weight即可。
整体代码一维滚动数组
def bag_problem():weight [1, 3, 4]value [15, 20, 30]bag_weight 4# 初始化: 全为0dp [0] * (bag_weight 1)# 先遍历物品, 再遍历背包容量for i in range(len(weight)):for j in range(bag_weight, weight[i] - 1, -1):# 递归公式这里注意不是value[i]而是weight[i]dp[j] max(dp[j], dp[j - weight[i]] weight[i])print(dp)bag_problem()416. 分割等和子集
416. 分割等和子集 解题思路 等分先判断总和能否被2整除能否进行分隔不能直接False能的话继续判断里面的数分隔后能否分成相等的两部分等分必然是总和值/2的值的大小的背包装满能装满则说明能等分不能装满则False。
二维数组
class Solution:def canPartition(self, nums: List[int]) - bool:# target既是背包大小也是最大价值问是否能装满target大小的背包target sum(nums)# 如果是奇数则不能均分直接False如果偶数则再后续加以判断if target%21:return Falseelse:target //2dp [[0]*(target1) for _ in range(len(nums))]# 遍历物品for i in range(len(nums)):# 遍历背包大小for j in range(target1):# 背包小鱼物品大小if jnums[i]:dp[i][j] dp[i-1][j]# 能放但不放或者放进去那个大取哪个else:dp[i][j] max(dp[i-1][j], dp[i-1][j-nums[i]]nums[i])return target dp[-1][-1]一维数组滚动数组
class Solution:def canPartition(self, nums: List[int]) - bool:# target既是背包大小也是最大价值问是否能装满target大小的背包target sum(nums)# 如果是奇数则不能均分直接False如果偶数则再后续加以判断if target%21:return Falseelse:target //2dp [0]*(target1)# 遍历物品for i in range(len(nums)):# 遍历背包大小逆序防止累加# for j in reversed(range(nums[i], target1)):for j in range(target, nums[i]-1, -1):dp[j] max(dp[j], dp[j-nums[i]]nums[i])return target dp[-1]1049. 最后一块石头的重量 II
1049. 最后一块石头的重量 II 该题与上一题很类似隐藏的背包问题。最终的思路是将这个石头集合分成两部分他们越相近即离和中值越近相差就越小。如果无法等分那么因为这个中值为向下取整所以离偏小的部分近一些离偏大的部分远一些。那么以中值为背包装满得到较小值部分的值求石头的总体和减去较小值部分就为最大值部分再减去一次较小值部分得出最小的相差。
为什么不求较大值呢因为较小值可以用中值找到最大背包而较大值的最大背包找不到。
一维滚动数组
class Solution:def lastStoneWeightII(self, stones: List[int]) - int:su_m sum(stones)target su_m//2dp [0]*(target1)for i in range(len(stones)):for j in range(target, stones[i]-1,-1):dp[j] max(dp[j], dp[j-stones[i]]stones[i])return su_m-dp[-1]-dp[-1]474. 一和零双维度背包
474. 一和零 二维背包问题分别装0和1的数量的背包两个数量用一个二维来存储。
class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) - int:dp [[0]*(n1) for _ in range(m1)]# 遍历物品for s in strs:ones s.count(1)zeros s.count(0)# 遍历二维背包for i in range(m, zeros-1, -1):for j in range(n, ones-1, -1):dp[i][j] max(dp[i][j], dp[i-zeros][j-ones]1)return dp[-1][-1]1.3.1.3、单次选择装满可能性总数
问题描述 有nnn件物品和一个最多能背重量为www的背包。第i件物品的重量是weight[i]weight[i]weight[i]每件物品只能用一次求解装满背包有哪些不同的方法。
分析 这次和之前遇到的背包问题不一样了之前都是求容量为j的背包最多能装多少。
本题则是装满有几种方法。其实这就是一个组合问题了。求组合类问题的公式都是类似这种 1. 确定dp[j]的含义 dp[j] 表示填满j包括j这么大容积的包有dp[j]种方法
2. 递推公式 只要获得nums[i]凑成dp[j]就有dp[j - nums[i]] 种方法。
例如dp[j]j 为5
如果那么已经有一个1nums[i] 的话有 dp[4]种方法 凑成 容量为5的背包已经有一个2nums[i] 的话有 dp[3]种方法 凑成 容量为5的背包已经有一个3nums[i] 的话有 dp[2]中方法 凑成 容量为5的背包已经有一个4nums[i] 的话有 dp[1]中方法 凑成 容量为5的背包已经有一个5 nums[i]的话有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢也就是把 所有的 dp[j - nums[i]] 累加起来。
dp[j] dp[j - nums[i]]这个公式在后面在讲解背包解决排列组合问题的时候还会用到。
3. 初始化 dp数组如何初始化 从递推公式可以看出在初始化的时候dp[0] 一定要初始化为1因为dp[0]是在公式中一切递推结果的起源如果dp[0]是0的话递推结果将都是0。
4. 遍历顺序 01背包问题一维dp的遍历nums放在外循环target在内循环且内循环倒序。
简单例子 有w4w4w4重量的背包 有n3n3n3件物品表示如下
重量 weight[i]物品02物品12物品24
问有多少种装满背包的方法 结果[2, 2], [4] 494. 目标和
494. 目标和 将该题转化为背包装满的装法次数。 使用推导公式
dp[j] dp[j-nums[i]]背包大小根据公式推导而来
leftright sum
left-right target
left (targetsum)/2初始化时需要赋值第一个值为1其余为0不变
dp[0]1举例推导 输入nums: [1, 1, 1, 1, 1], S: 3
bagSize (S sum) / 2 (3 5) / 2 4
dp数组状态变化如下
代码整体如下
class Solution:def findTargetSumWays(self, nums: List[int], target: int) - int:# leftright sum# left-right target# left (targetsum)/2s_um sum(nums)# 目标值比所有值求和大或者目标值不可分那么方法为0if abs(target)s_um or (targets_um)%2:return 0# 背包大小根据上面公式推导bagsize (targets_um)//2# 创建dp表dp [0]*(bagsize1)# 初始化第一个元素为1dp[0]1# 同前面的二重循环for i in range(len(nums)):for j in range(bagsize, nums[i]-1, -1):# 递推公式用来求背包装满的次数dp[j] dp[j-nums[i]]return dp[-1]注意 有道题 39. 组合总和 大部分是使用回溯算法来做的为什么不选用动态规划呢因为题目所求的结果不同
求个数列出组合动态规划回溯爆搜
总结
01背包最大重量/价值01背包最大重量/价值01背包可能性总数维度二维一维一维初始化第0行和第0列分别初始化无需初始化初始化dp[0]1内外循序物品背包 | 背包物品物品背包物品背包物品顺序正序|逆序正序|逆序正序|逆序背包顺序正序|逆序逆序逆序递推公式dp[i][j]max(dp[i-1]j[j], dp[i-1][j-weight[i]]value[i])dp[j]max(dp[j], dp[j-weight[i]]value[i])dp[j]dp[j-nums[i]]1.3.2、完全背包
完全背包和01背包问题唯一不同的地方就是每种物品有无限件。 1.3.2.1、重复选择最大价值
问题描述 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品都有无限个也就是可以放入背包多次求解将哪些物品装入背包里物品价值总和最大。
简单例子 有w4w4w4重量的背包 有n∞n\inftyn∞件物品表示如下
重量 weight[i]价值 value[i]物品0115物品1320物品2430
问背包能背的物品的最大价值是多少
对比下 01背包的核心代码如下
# 先遍历物品再遍历背包
# 遍历物品
for i in range(len(weight)):# 遍历背包容量for j in range(bagWeight, weight[i]-1, -1):dp[j] max(dp[j], dp[j - weight[i]]value[i])我们知道01背包内嵌的循环是从大到小遍历为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的所以要从小到大去遍历即
# 先遍历物品再遍历背包
# 遍历物品
for i in range(len(weight)):# 遍历背包容量for j in range(weight[i], bagWeight1):dp[j] max(dp[j], dp[j-weight[i]]value[i])01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了一维dp数组的两个for循环先后循序一定是先遍历物品再遍历背包容量。
在完全背包中对于一维dp数组来说其实两个for循环嵌套顺序是无所谓的。
因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
遍历物品在外层循环遍历背包容量在内层循环状态如图 遍历背包容量在外层循环遍历物品在内层循环状态如图 看了这两个图大家就会理解完全背包中两个for循环的先后循序都不影响计算dp[j]所需要的值这个值就是下标j之前所对应的dp[j]。
先遍历背包再遍历物品代码如下
# 先遍历背包再遍历物品
# 遍历背包
for j in range(bagWeight1):# 遍历物品for i in range(len(weight)):if j-weight[i]0:dp[j] max(dp[j-weight[i]]value[i])整体代码
# 先遍历物品再遍历背包
def bag_pack1():weight [1, 3, 4]value [15, 20, 30]bag_weight 4dp [0]*(bag_weight 1)for i in range(len(weight)):for j in range(weight[i], bag_weight 1):dp[j] max(dp[j], dp[j - weight[i]] value[i])print(dp[bag_weight])# 先遍历背包再遍历物品
def bag_pack2():weight [1, 3, 4]value [15, 20, 30]bag_weight 4dp [0]*(bag_weight 1)for j in range(bag_weight 1):for i in range(len(weight)):if j weight[i]: dp[j] max(dp[j], dp[j - weight[i]] value[i])print(dp[bag_weight])if __name__ __main__:bag_pack1()bag_pack2()总结 因为是完全背包物品可叠加那么一维数组顺序遍历即可
01背包最大重量/价值01背包最大重量/价值01背包可能性总数完全背包最大重量/价值维度二维一维一维一维初始化第0行和第0列分别初始化无需初始化初始化dp[0]1无需初始化内外循序物品背包 | 背包物品物品背包物品背包物品背包|背包物品物品顺序正序|逆序正序|逆序正序|逆序正序|逆序背包顺序正序|逆序逆序(避免重复)逆序正序(为了重复)递推公式dp[i][j]max(dp[i-1]j[j], dp[i-1][j-weight[i]]value[i])dp[j]max(dp[j], dp[j-weight[i]]value[i])dp[j]dp[j-nums[i]]dp[i][j]max(dp[i-1]j[j], dp[i-1][j-weight[i]]value[i])1.3.2.2、重复选择组合装满可能性总数
518. 零钱兑换 II组合问题
518. 零钱兑换 II
递推公式 求背包装满的次数根据公式dp[j] dp[j-nums[i]]
遍历顺序 因为纯完全背包求得装满背包的最大价值是多少和凑成总和的元素有没有顺序没关系即有顺序也行没有顺序也行。所以纯完全背包是能凑成总和就行不用管怎么凑的。
而本题要求凑成总和的组合数元素之间明确要求没有顺序那么每个方案个数是为组合数。
那么本题两个for循环的先后顺序可就有说法了。
结果是求组合数那么遍历顺序为 先遍历物品后遍历背包
# 遍历物品
for i in range(len(coins)):# 遍历背包容量for j in range(coins[i], amount1):dp[j] dp[j-coins[i]]如果是求排列数那么遍历顺序为
# 遍历背包容量
for j in range(amount1):# 遍历物品for i in range(len(coins)):if j-coins[i]0:dp[j]dp[j-coins[i]]整体代码
class Solution:def change(self, amount: int, coins: List[int]) - int:dp [0]*(amount1)dp[0]1for i in range(len(coins)):for j in range(coins[i], amount1):dp[j]dp[j-coins[i]]return dp[-1]总结 通过该例子我们知道在完全背包问题的装满可能性总数中物品和背包的顺序在排列和组合问题中是有影响的
排列组合背包物品物品背包
综上
01背包最大重量/价值01背包最大重量/价值01背包可能性总数完全背包最大重量/价值完全背包可能性总数维度二维一维一维一维一维初始化第0行和第0列分别初始化无需初始化初始化dp[0]1无需初始化初始化dp[0]1内外循序物品背包 | 背包物品物品背包物品背包物品背包|背包物品排列: 背包物品|组合: 物品背包物品顺序正序|逆序正序|逆序正序|逆序正序|逆序正序|逆序背包顺序正序|逆序逆序(避免重复)逆序正序(为了重复)正序递推公式dp[i][j]max(dp[i-1]j[j], dp[i-1][j-weight[i]]value[i])dp[j]max(dp[j], dp[j-weight[i]]value[i])dp[j]dp[j-nums[i]]dp[i][j]max(dp[i-1]j[j], dp[i-1][j-weight[i]]value[i])dp[j]dp[j-nums[i]]1.3.2.3、重复选择排列装满可能性总数
377. 组合总和 Ⅳ
377. 组合总和 Ⅳ 完全背包两个循环顺序执行 求次数dp[j] dp[j-nums[i]]并且dp[0]1 求排列先背包后物品。
根据上一题的规律可以很轻易的做出此题
class Solution:def combinationSum4(self, nums: List[int], target: int) - int:dp [0]*(target1)dp[0]1for j in range(target1):for i in nums:if j-i0:dp[j]dp[j-i]return dp[-1]70. 爬楼梯
70. 爬楼梯 同上题的思路这是背包里求排列问题即1、2 步 和 2、1 步都是上三个台阶但是这两种方法不一样。所以需将target放在外循环将nums放在内循环。每一步可以走多次这是完全背包内循环需要从前向后遍历。
class Solution:def climbStairs(self, n: int) - int:dp [0]*(n1)dp[0]1# 遍历背包数楼梯总长度for j in range(n1):# 遍历物品台阶数1或2 for i in [1,2]:if j-i0:dp[j]dp[j-i]return dp[-1]139. 单词拆分
139. 单词拆分
1.dp数组含义 dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词。
2.递推公式 如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是true。j i 。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true。
3.dp数组的初始化 从递推公式中可以看出dp[i] 的状态依靠 dp[j]是否为true那么dp[0]就是递推的根基dp[0]一定要为true否则递推下去后面都都是false了。
下标非0的dp[i]初始化为false只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。
4.遍历顺序 题目中说是拆分为一个或多个在字典中出现的单词所以这是完全背包。 “apple”, “pen” 是物品那么我们要求 物品的组合一定是 “apple” “pen” “apple” 才能组成 “applepenapple”。
“apple” “apple” “pen” 或者 “pen” “apple” “apple” 是不可以的那么我们就是强调物品之间顺序。
所以说本题一定是 先遍历 背包再遍历物品。所以是排列问题。
5.举例推导dp[i] 以输入: s “leetcode”, wordDict [“leet”, “code”]为例dp状态如图
所以整体代码如下
class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:dp [False]*(len(s)1)dp[0]True# 排列问题先背包for j in range(1, len(s)1):# 后物品即单词for i in wordDict:if jlen(i):dp[j] dp[j] or dp[j-len(i)] and s[j-len(i):j]ireturn dp[-1]1.3.2.4、重复选择 装满的最少数量
322. 零钱兑换
322. 零钱兑换
1.dp数组的含义: dp[j]凑足总额为j所需钱币的最少个数为dp[j]
2.递推公式 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1就是dp[j]考虑coins[i]所以dp[j] 要取所有 dp[j - coins[i]] 1 中最小的。
求最小次数dp[j] min(dp[j], dp[j - coin[i]] 1)
3.数组初始化 dp数组如何初始化 首先凑足总金额为0所需钱币的个数一定是0那么dp[0] 0;
其他下标对应的数值呢考虑到递推公式的特性如果默认初始化为0那么每次求min的时候都会取默认值0而不是真实最小值那么默认0就不可取。所以dp[j]必须初始化为一个最大的数否则就会在min(dp[j - coins[i]] 1, dp[j])比较的过程中被初始值覆盖。所以下标非0的元素都是应该是最大值。
代码如下
dp [float(inf)]*(amount1)
dp[0] 14.遍历顺序 求所需钱币最小个数所以并不讲究物品和背包的先后顺序因为既不是排列也不是组合。
5.举例推导dp数组 以输入coins [1, 2, 5], amount 5为例 整理代码如下
class Solution:def coinChange(self, coins: List[int], amount: int) - int:版本一# 初始化dp [float(inf)]*(amount 1)dp[0] 0# 遍历物品for coin in coins:# 遍历背包for j in range(coin, amount 1):dp[j] min(dp[j], dp[j - coin] 1)return dp[amount] if dp[amount] ! float(inf) else -1def coinChange1(self, coins: List[int], amount: int) - int:版本二# 初始化dp [float(inf)]*(amount 1)dp[0] 0# 遍历物品for j in range(1, amount 1):# 遍历背包for coin in coins:if j coin:dp[j] min(dp[j], dp[j - coin] 1)return dp[amount] if dp[amount] ! float(inf) else -1总结
01背包最大重量/价值01背包最大重量/价值01背包可能性总数完全背包最大重量/价值完全背包可能性总数完全背包最少数量维度二维一维一维一维一维一维初始化第0行和第0列分别初始化无需初始化初始化dp[0]1无需初始化初始化dp[0]1dp [float(“inf”)]*(amount 1) dp[0] 0内外循序物品背包 | 背包物品物品背包物品背包物品背包|背包物品排列: 背包物品|组合: 物品背包背包物品|物品背包物品顺序正序|逆序正序|逆序正序|逆序正序|逆序正序|逆序正序背包顺序正序|逆序逆序(避免重复)逆序正序(为了重复)正序正序递推公式dp[i][j]max(dp[i-1]j[j], dp[i-1][j-weight[i]]value[i])dp[j]max(dp[j], dp[j-weight[i]]value[i])dp[j]dp[j-nums[i]]dp[i][j]max(dp[i-1]j[j], dp[i-1][j-weight[i]]value[i])dp[j]dp[j-nums[i]]dp[j] min(dp[j], dp[j - coin[i]] 1)279. 完全平方数
279. 完全平方数
这题同上一题零钱兑换思路类似不过得自创平方数集合作为物品。
class Solution:def numSquares(self, n: int) - int:nums [i*i for i in range(1, n1) if i*in]dp [float(inf)]*(n1)dp[0]0# 先遍历物品再遍历背包for i in nums:for j in range(i, n1):dp[j] min(dp[j], dp[j-i]1)return dp[-1]也可以先遍历背包再遍历物品
# 遍历背包for j in range(1, n 1):# 遍历物品for num in nums:if j num:dp[j] min(dp[j], dp[j - num] 1)1.3.3、多重背包
这个问题与 0-1 背包的区别在于0-1 背包中每种物品有且只有一个而多重背包中一种物品有nums[i] 个。
对于多重背包我在力扣上还没发现对应的题目所以这里就做一下简单介绍大家大概了解一下。
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用每件耗费的空间是Ci 价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量且价值总和最大。
多重背包和01背包是非常像的 为什么和01背包像呢
每件物品最多有Mi件可用把Mi件摊开其实就是一个01背包问题了。
例如
背包最大重量为10。
物品为
重量 weight[i]价值 value[i]数量物品01152物品13203物品24302
问背包能背的物品最大价值是多少
和如下情况有区别么
重量 weight[i]价值 value[i]数量物品01151物品01151物品13201物品13201物品13201物品24301物品24301毫无区别这就转成了一个01背包问题了且每个物品只用一次。
这种方式来实现多重背包的代码如下
def test_multi_pack1():版本一改变物品数量为01背包格式weight [1, 3, 4]value [15, 20, 30]nums [2, 3, 2]bag_weight 10for i in range(len(nums)):# 将物品展开数量为1while nums[i] 1:weight.append(weight[i])value.append(value[i])nums[i] - 1dp [0]*(bag_weight 1)# 遍历物品for i in range(len(weight)):# 遍历背包for j in range(bag_weight, weight[i] - 1, -1):dp[j] max(dp[j], dp[j - weight[i]] value[i])print( .join(map(str, dp))if __name__ __main__:test_multi_pack1()时间复杂度O(m × n × k)m物品种类个数n背包容量k单类物品数量 也有另一种实现方式就是把每种商品遍历的个数放在01背包里面在遍历一遍。
代码如下详看注释
def test_multi_pack2():版本改变遍历个数weight [1, 3, 4]value [15, 20, 30]nums [2, 3, 2]bag_weight 10dp [0]*(bag_weight 1)for i in range(len(weight)):for j in range(bag_weight, weight[i] - 1, -1):# 以上是01背包加上遍历个数for k in range(1, nums[i] 1):if j - k*weight[i] 0:dp[j] max(dp[j], dp[j - k*weight[i]] k*value[i])print( .join(map(str, dp)))if __name__ __main__:test_multi_pack2()时间复杂度O(m × n × k)m物品种类个数n背包容量k单类物品数量 从代码里可以看出是01背包里面在加一个for循环遍历一个每种商品的数量。 和01背包还是如出一辙的。
当然还有那种二进制优化的方法其实就是把每种物品的数量打包成一个个独立的包。
和以上在循环遍历上有所不同因为是分拆为各个包最后可以组成一个完整背包具体原理我就不做过多解释了大家了解一下就行面试的话基本不会考完这个深度了感兴趣可以自己深入研究一波。
总结 多重背包在面试中基本不会出现力扣上也没有对应的题目大家对多重背包的掌握程度知道它是一种01背包并能在01背包的基础上写出对应代码就可以了。
至于背包九讲里面还有混合背包二维费用背包分组背包等等这些大家感兴趣可以自己去学习学习这里也不做介绍了面试也不会考。 参考
Algorithm and Data Structure Notes LeetCode BackPack 背包问题 代码随想录 随想录视频 1.4、打家劫舍
1.4.1、198. 打家劫舍
198. 打家劫舍 每个家庭有不同金钱数量盗窃的家庭不能相邻求最大盗窃金额。
class Solution:def rob(self, nums: List[int]) - int:if len(nums)1:return nums[-1]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-2]nums[i], dp[i-1])return dp[-1]1.4.2、213. 打家劫舍 II
213. 打家劫舍 II 承接上题但是房子是环状即首位相连的。
那么要考虑第一个房子和最后一个房子会相临只能取其一。
所以我们把房子变成两种情况
不考虑第一个房子 nums[1:]不考虑最后一个房子nums[:-1]
以上两种情况取最大值后再去他们两个之间的最大值可以通过上题的解法来解了
class Solution:def rob(self, nums: List[int]) - int:if len(nums)1:return nums[-1]def roblist(nums):if len(nums)1:return nums[-1]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]return max(roblist(nums[1:]), roblist(nums[:-1]))1.4.3、337.打家劫舍 III
337.打家劫舍 III 题目思路类似第一种类型但是需要掌握二叉树的遍历。
class Solution:def rob(self, root: Optional[TreeNode]) - int:# dp数组dp table以及下标的含义# 1. 下标为 0 记录 **不偷该节点** 所得到的的最大金钱# 2. 下标为 1 记录 **偷该节点** 所得到的的最大金钱dp self.traversal(root)return max(dp)# 要用后序遍历, 因为要通过递归函数的返回值来做下一步计算def traversal(self, node):# 递归终止条件就是遇到了空节点那肯定是不偷的if not node:return (0, 0)left self.traversal(node.left)right self.traversal(node.right)# 不偷当前节点, 偷子节点val_0 max(left[0], left[1]) max(right[0], right[1])# 偷当前节点, 不偷子节点val_1 node.val left[0] right[0]return (val_0, val_1)1.5、股票问题
像这样的股票问题使用动态规划创建两列即两个状态的二维数组照常初始化但需要根据题意去得出特定的递推公式便可完成该题。 1.5.1、121. 买卖股票的最佳时机 - 只能买卖一次
121. 买卖股票的最佳时机
贪心算法
class Solution:def maxProfit(self, prices: List[int]) - int:low float(inf)result 0# 遍历每一个值当做最大值其中可能存在最小值进行替换# 右边当最大值在其左边找最小值for i in range(len(prices)):low min(low, prices[i])result max(result, prices[i]-low)return result递推公式两种状态 要么持有该股票那么要么之前就买了dp[i-1][0]保持原样要么刚买-prices[i] 要么不持有该股票那么之前就没买dp[i-1][1]也保持原样要么刚卖prices[i]dp[i-1]取差值。
动态规划
class Solution:def maxProfit(self, prices: List[int]) - int:# 创建二维数组两个状态持有和不持有length len(prices)if length0:return 0dp [[0, 0] for _ in range(length)]# 初始化第一天持有则买入第一天不持有则仍然为0dp[0][0] -prices[0]dp[0][1] 0# 开始遍历for i in range(1, length):# 持有股票dp[i][0] max(dp[i-1][0], -prices[i])# 不持有股票dp[i][1] max(dp[i-1][1], prices[i]dp[i-1][0])return dp[-1][1]滚动数组
class Solution:def maxProfit(self, prices: List[int]) - int:length len(prices)dp [[0] * 2 for _ in range(2)] #注意这里只开辟了一个2 * 2大小的二维数组dp[0][0] -prices[0]dp[0][1] 0for i in range(1, length):dp[i % 2][0] max(dp[(i-1) % 2][0], -prices[i])dp[i % 2][1] max(dp[(i-1) % 2][1], prices[i] dp[(i-1) % 2][0])return dp[(length-1) % 2][1]进一步改进
class Solution:def maxProfit(self, prices: List[int]) - int:length len(prices)dp0, dp1 -prices[0], 0 #注意这里只维护两个常量因为dp0的更新不受dp1的影响for i in range(1, length):dp1 max(dp1, dp0 prices[i])dp0 max(dp0, -prices[i])return dp11.5.2、122. 买卖股票的最佳时机 II - 能买卖多次
122. 买卖股票的最佳时机 II 这里重申一下dp数组的含义
dp[i][0] 表示第i天持有股票所得现金。 dp[i][1] 表示第i天不持有股票所得最多现金
如果第i天持有股票即dp[i][0] 那么可以由两个状态推出来
第i-1天就持有股票那么就保持现状所得现金就是昨天持有股票的所得现金 即dp[i - 1][0]第i天买入股票所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即dp[i - 1][1] - prices[i] 注意这里和121. 买卖股票的最佳时机 唯一不同的地方就是推导dp[i][0]的时候第i天买入股票的情况。
在121. 买卖股票的最佳时机 中因为股票全程只能买卖一次所以如果买入股票那么第i天持有股票即dp[i][0]一定就是 -prices[i]。
而本题因为一只股票可以买卖多次所以当第i天买入股票的时候所持有的现金可能有之前买卖过的利润。那么第i天持有股票即dp[i][0]如果是第i天买入股票所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即dp[i - 1][1] - prices[i]。
再来看看如果第i天不持有股票即dp[i][1]的情况 依然可以由两个状态推出来
第i-1天就不持有股票那么就保持现状所得现金就是昨天不持有股票的所得现金 即dp[i - 1][1]第i天卖出股票所得现金就是按照今天股票价格卖出后所得现金即prices[i] dp[i - 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)):#注意这里是和121. 买卖股票的最佳时机唯一不同的地方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]滚动数组
class Solution:def maxProfit(self, prices: List[int]) - int:length len(prices)dp [[0] * 2 for _ in range(2)] #注意这里只开辟了一个2 * 2大小的二维数组dp[0][0] -prices[0]dp[0][1] 0for i in range(1, length):dp[i % 2][0] max(dp[(i-1) % 2][0], dp[(i-1) % 2][1] - prices[i])dp[i % 2][1] max(dp[(i-1) % 2][1], dp[(i-1) % 2][0] prices[i])return dp[(length-1) % 2][1]其他解法
class Solution:def maxProfit(self, prices: List[int]) - int:# 创建dp table# 含义第N天的最大利润dp [0] * (len(prices)1)# 初始化第0天和第一天没有利润为0当然这里多余# dp[0] dp[1] 0# 从第二天开始产生正负利润for i in range(2, len(prices)1):# 当前第N天的利润等于max(之前的利润今天的利润之前的利润)# 这里取最大值若今天产生负利润则不买只取之前的利润dp[i] max(dp[i-1], prices[i-1]-prices[i-2]dp[i-1])return dp[-1]1.5.3、123. 买卖股票的最佳时机 III
123. 买卖股票的最佳时机 III
class Solution:def maxProfit(self, prices: List[int]) - int:if len(prices) 0:return 0dp [[0] * 5 for _ in range(len(prices))]dp[0][1] -prices[0]dp[0][3] -prices[0]for i in range(1, len(prices)):dp[i][0] dp[i-1][0]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][4]官方降低复杂度解法
class Solution:def maxProfit(self, prices: List[int]) - int:if len(prices) 0:return 0dp [0] * 5 dp[1] -prices[0]dp[3] -prices[0]for i in range(1, len(prices)):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])dp[4] max(dp[4], dp[3] prices[i])return dp[4]1.5.4、188. 买卖股票的最佳时机 IV
188. 买卖股票的最佳时机 IV
class Solution:def maxProfit(self, k: int, prices: List[int]) - int:if len(prices) 0:return 0dp [[0] * (2*k1) for _ in range(len(prices))]for j in range(1, 2*k, 2):dp[0][j] -prices[0]for i in range(1, len(prices)):for j in range(0, 2*k-1, 2):dp[i][j1] max(dp[i-1][j1], dp[i-1][j] - prices[i])dp[i][j2] max(dp[i-1][j2], dp[i-1][j1] prices[i])return dp[-1][2*k]滚动数组
class Solution:def maxProfit(self, k: int, prices: List[int]) - int:if len(prices) 0: return 0dp [0] * (2*k 1)for i in range(1,2*k,2):dp[i] -prices[0]for i in range(1,len(prices)):for j in range(1,2*k 1):if j % 2:dp[j] max(dp[j],dp[j-1]-prices[i])else:dp[j] max(dp[j],dp[j-1]prices[i])return dp[2*k]1.5.5、309. 最佳买卖股票时机含冷冻期
309. 最佳买卖股票时机含冷冻期
class Solution:def maxProfit(self, prices: List[int]) - int:n len(prices)if n 0:return 0dp [[0] * 4 for _ in range(n)]dp[0][0] -prices[0] #持股票for i in range(1, n):dp[i][0] max(dp[i-1][0], max(dp[i-1][3], dp[i-1][1]) - prices[i])dp[i][1] max(dp[i-1][1], dp[i-1][3])dp[i][2] dp[i-1][0] prices[i]dp[i][3] dp[i-1][2]return max(dp[n-1][3], dp[n-1][1], dp[n-1][2])1.5.6、714. 买卖股票的最佳时机含手续费
714. 买卖股票的最佳时机含手续费
class Solution:def maxProfit(self, prices: List[int], fee: int) - int:n len(prices)dp [[0] * 2 for _ in range(n)]dp[0][0] -prices[0] #持股票for i in range(1, n):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] - fee)return max(dp[-1][0], dp[-1][1])1.5、子序列问题
1.5.1、子序列不连续
1.5.1.1、300. 最长上升子序列
力扣题目链接 从左开始遍历每个点再从左到该点进行遍历和比较比它小则累加这种加法保证了是有序的。
class Solution:def lengthOfLIS(self, nums: List[int]) - int:# 全部初始化为最小的子序列1用来存储该位置的最小子序列dp [1]*len(nums)dp[0]1for i in range(1, len(nums)):# 因为是非连续的子序列所以需要遍历前面所有点for j in range(i):if nums[j]nums[i]:dp[i] max(dp[i], dp[j]1)return max(dp)1.5.1.2、1143. 最长公共子序列
力扣题目链接
注意与 1.5.2.2、718. 最长重复子数组 的区分可以先尝试做718. 最长重复子数组再来尝试这题。
这题要考虑不连续的公共子串匹配不相等时该如何处理值 有三个方向推到dp[i][j]斜对角为匹配相等时前面匹配的字符这次匹配到一次也就是1匹配不相等时上和左取最大值取上可能这一行都不匹配取左可能前面有匹配的而后面不匹配。
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) - int:dp [[0]*(len(text2)1) for _ in range(len(text1)1)]for i in range(1, len(text1)1):for j in range(1, len(text2)1):if text1[i-1] text2[j-1]:# 匹配相等把斜上角的值填过来1斜上角为各个字符串上一步匹配相等的次数dp[i][j] dp[i-1][j-1] 1else:# dp[i][j-1]有过相等但后续匹配不相等时把左一个值向右填充# dp[i-1][j]匹配完全不相等把上一个值向下填充# dp[i][j-1], text2在该字母上的最大子序列# dp[i-1][j], text1在该字母上的最大子序列# 两个字母不相等dp[i][j] max(dp[i-1][j], dp[i][j-1])return dp[-1][-1]这一题是公共连续序列对于其拓展还有题型 最长公共子串 1.5.1.3、1035. 不相交的线
力扣题目链接 连线是有序的实际上是求最大公共子序列。 求两个字符串的公共子序列则需要二元数组。
class Solution:def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) - int:dp [[0]*(len(nums2)1) for _ in range(len(nums1)1)]for i in range(1, len(nums1)1):for j in range(1, len(nums2)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])print(dp)return dp[-1][-1]这一题的本质是与 1.5.1.2、1143. 最长公共子序列 相同代码与过程分析相同。 1.5.2、子序列连续
1.5.2.1、674. 最长连续递增序列
力扣题目链接
这道题注意和上个单元的 1.5.1.1、300. 最长上升子序列 的区分连续和不连续。
class Solution:def findLengthOfLCIS(self, nums: List[int]) - int:dp [1]*len(nums)# 这里只用一层循环因为是连续子串所以只用比较相邻的值就行for i in range(1, len(nums)):if nums[i]nums[i-1]:dp[i] dp[i-1]1return max(dp)或者 增加些内存来减少用时
class Solution:def findLengthOfLCIS(self, nums: List[int]) - int:dp [1]*len(nums)result 1for i in range(1, len(nums)):if nums[i]nums[i-1]:dp[i] dp[i-1]1if dp[i]result:result dp[i]return result1.5.2.2、718. 最长重复子数组
力扣题目链接
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) - int:# 这里创建二维dp table记录两个字符串的匹配数(注意i与j的顺序)dp [[0]*(len(nums2)1) for _ in range(len(nums1)1)]# 取最大值result 0# 两层循环遍历两个字符串顺序可以调换for i in range(1, len(nums1)1):for j in range(1, len(nums2)1):# 判断当前索引的值是否相等if nums1[i-1]nums2[j-1]:# 等于各个前面一个的值的匹配数1dp[i][j] dp[i-1][j-1]1if dp[i][j]result:result dp[i][j]return result时间复杂度O(n×m)O(n × m)O(n×m)n 为A长度m为B长度 空间复杂度O(n×m)O(n × m)O(n×m)
滚动数组 时间复杂度O(n×m)O(n × m)O(n×m)n 为A长度m为B长度 空间复杂度O(m)O(m)O(m) 1.5.2.3、53. 最大子序和
力扣题目链接
class Solution:def maxSubArray(self, nums: List[int]) - int:# 从0到第i个数的最大值dp [0]*(len(nums))# 初始化第一个dp[0] nums[0]# 从第二个开始遍历for i in range(1, len(nums)):# 前一个最大值该索引的值是否大大就相加不大就只保留索引值dp[i] max(nums[i], nums[i]dp[i-1])return max(dp) 1.5.3、编辑距离
1.5.3.1、392. 判断子序列
力扣题目链接
思路同上两个字符串比较最大公共子序列
class Solution:def isSubsequence(self, s: str, t: str) - bool:dp [[0]*(len(t)1) for _ in range(len(s)1)]for i in range(1, len(s)1):for j in range(1, len(t)1):if s[i-1]t[j-1]:dp[i][j] dp[i-1][j-1]1else:# dp[i-1][j]表示不匹配时是否把上一个结果往下移动# 不加会又从0开始加会少1一次总之结果都会比length少dp[i][j] dp[i][j-1]# 也可以dp[i][j] max(dp[i][j-1], dp[i-1][j])if dp[-1][-1]len(s):return Truereturn False1.5.3.2、115. 不同的子序列
力扣题目链接
class Solution:def numDistinct(self, s: str, t: str) - int:# dp table 出现的个数dp [[0]*(len(s)1) for _ in range(len(t)1)]# t若为空则在s中都能出现一次所以第一行初始化为1for i in range(len(s)1):dp[0][i] 1# s为空则不能被t的任何任何字母组成# 所以 dp[i][0] 0不变# i到前面的字母(t) 出现在 j到之前的字母(s) 出现的次数for i in range(1, len(t)1):for j in range(1, len(s)1):if t[i-1] s[j-1]:# dp[i-1][j-1] 两个字符串s与t退一个字母匹配的次数# dp[i][j-1] s字符串 向左退一次匹配的次数前面有重复的就会累加dp[i][j] dp[i-1][j-1]dp[i][j-1]else:dp[i][j] dp[i][j-1]return dp[-1][-1]1.5.3.3、583. 两个字符串的删除操作
力扣题目链接 确定递推公式 当word1[i - 1] 与 word2[j - 1]相同的时候 当word1[i - 1] 与 word2[j - 1]不相同的时候 当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 - 1][j] 1
情况二删word2[j - 1]最少操作次数为dp[i][j - 1] 1
情况三同时删word1[i - 1]和word2[j - 1]操作的最少次数为dp[i - 1][j - 1] 2
那最后当然是取最小值所以当word1[i - 1] 与 word2[j - 1]不相同的时候递推公式dp[i][j] min({dp[i - 1][j - 1] 2, dp[i - 1][j] 1, dp[i][j - 1] 1})
class Solution:def minDistance(self, word1: str, word2: str) - int:# 建表dp [[0]*(len(word2)1) for _ in range(len(word1)1)]# 初始化for i in range(len(word2)1):dp[0][i]ifor i in range(len(word1)1):dp[i][0]i# 填表for i in range(1, len(word1)1):for j in range(1, len(word2)1):if word1[i-1] word2[j-1]:dp[i][j] dp[i-1][j-1]else:# word1删除word2删除word1和word2都删除一个dp[i][j] min(dp[i-1][j]1, dp[i][j-1]1, dp[i-1][j-1]2)return dp[-1][-1]1.5.3.4、72. 编辑距离
力扣题目链接
class Solution:def minDistance(self, word1: str, word2: str) - int:dp [[0]*(len(word2)1) for _ in range(len(word1)1)]# 初始化删除为空值需要的步数for i in range(len(word2)1):dp[0][i] ifor i in range(len(word1)1):dp[i][0] i# 循环for i in range(1, len(word1)1):for j in range(1, len(word2)1):if word1[i-1] word2[j-1]:dp[i][j] dp[i-1][j-1]else:# 删除word1删除word2替换word1和word2. 1都是一次操作dp[i][j] min(dp[i-1][j]1, dp[i][j-1]1, dp[i-1][j-1]1)return dp[-1][-1]1.5.4、回文
1.5.4.1、647. 回文子串
力扣题目链接
确定dp数组dp table以及下标的含义 布尔类型的dp[i][j]表示区间范围[i,j] 注意是左闭右闭的子串是否是回文子串如果是dp[i][j]为true否则为false。确定递推公式 整体上是两种就是s[i]与s[j]相等s[i]与s[j]不相等这两种。 当s[i]与s[j]不相等dp[i][j]一定是false。 当s[i]与s[j]相等时有如下三种情况: 情况一下标i 与 j相同同一个字符例如a当然是回文子串 情况二下标i 与 j相差为1例如aa也是回文子串 情况三下标i 与 j相差大于1的时候例如cabac此时s[i]与s[j]已经相同了我们看i到j区间是不是回文子串就看aba是不是回文就可以了那么aba的区间就是 i1 与 j-1区间这个区间是不是回文就看dp[i 1][j - 1]是否为true。
递归公式
if s[i] s[j]:if j-i1:result1dp[i][j] Trueelse if dp[i1][j-1]:result1dp[i][j] Trueresult就是统计回文子串的数量。
这里没有列出当s[i]与s[j]不相等的时候因为在下面dp[i][j]初始化的时候就初始为false。 dp数组如何初始化 dp[i][j]不能初始化为true这就表示全都匹配上了。所以dp[i][j]初始化为false。 确定遍历顺序 首先从递推公式中可以看出情况三是根据dp[i 1][j - 1]是否为true在对dp[i][j]进行赋值true的。
dp[i 1][j - 1] 在 dp[i][j]的左下角如图 如果这矩阵是从上到下从左到右遍历那么会用到没有计算过的dp[i 1][j - 1]也就是根据不确定是不是回文的区间[i1,j-1]来判断了[i,j]是不是回文那结果一定是不对的。
所以一定要从下到上从左到右遍历这样保证dp[i 1][j - 1]都是经过计算的。
有的代码实现是优先遍历列然后遍历行其实也是一个道理都是为了保证dp[i 1][j - 1]都是经过计算的。
举例推导dp数组 举例输入“aaa”dp[i][j]状态如下 图中有6个true所以就是有6个回文子串。
注意因为dp[i][j]的定义所以j一定是大于等于i的那么在填充dp[i][j]的时候一定是只填充右上半部分。
综上代码如下:
动态规划
class Solution:def countSubstrings(self, s: str) - int:# 暴力求解是双循环所以这里创建仿造创建二元数组dp [[False]*(len(s)) for _ in range(len(s))]result 0# 从后往前遍历for i in range(len(s)-1, -1, -1):for j in range(i, len(s)):# 字符串字母相同if s[i]s[j]:# 自身或者相邻if j-i1:dp[i][j]Trueresult1# 不相邻相隔大于1# 该字符串是否为回文首字母1结尾字母-1# 就是前后都往内部缩一个字母是否为回文elif dp[i1][j-1]:dp[i][j]Trueresult1return result时间复杂度O(n^2) 空间复杂度O(n^2)
暴力遍历 双层循环每次后移一个字母判断回文
class Solution:def countSubstrings(self, s: str) - int:result 0# 暴力遍历for i in range(1, len(s)1):for j in range(i):if s[j:i] s[j:i][::-1]:result1return result双指针法
class Solution:def countSubstrings(self, s: str) - int:result 0for i in range(len(s)):# 以i为中心result self.extend(s, i, i, len(s))# 以i1为中心result self.extend(s, i, i1, len(s))return resultdef extend(self, s, i, j, n):res 0while i0 and jn and s[i]s[j]:i-1j1res1return res时间复杂度O(n^2) 空间复杂度O(1) 1.5.4.2、最长回文子串
HJ32 密码截取 - 牛客网
import sysfor line in sys.stdin:line line[:-1]# dp[i][j]表示从i到j是否为回文# create dp tabledp [[0]*len(line) for _ in range(len(line))]# initial tablefor i in range(len(line)):dp[i][i]1max_long 0# go through table# 一头一尾开始遍历行逆序for i in range(len(line)-1, -1, -1):for j in range(i1, len(line)):# 字母相等if line[i] line[j]:# 判断中间字符是否相等或者两个字符相邻无中间字符if dp[i1][j-1] or j-i1:# 加上i和j上的两个字符dp[i][j] dp[i1][j-1]2# 去掉非连续# else:# dp[i][j] max(dp[i1][j], dp[i][j-1])# 每一次起点遍历保存最大值if max_longmax(dp[i]):max_long max(dp[i])print(max_long)这里可以像上题一样的写法先不初始化双循环内的判断条件可以改为1.奇i-j02.偶i-j13.大于2的情况除开两端的中间为回文即 1.5.4.3、516. 最长回文子序列
力扣题目链接 这一题与上一题的区别回文子串是要连续的回文子序列可不是连续的。
确定dp数组dp table以及下标的含义 dp[i][j]字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。确定递推公式 如果s[i]与s[j]相同那么dp[i][j] dp[i 1][j - 1] 2 如果s[i]与s[j]不相同说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。 加入s[j]的回文子序列长度为dp[i 1][j]。 加入s[i]的回文子序列长度为dp[i][j - 1]。 那么dp[i][j]一定是取最大的即dp[i][j] max(dp[i 1][j], dp[i][j - 1]) dp数组如何初始化 首先要考虑当i 和j 相同的情况从递推公式dp[i][j] dp[i 1][j - 1] 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。 所以需要手动初始化一下当i与j相同那么dp[i][j]一定是等于1的即一个字符的回文子序列长度就是1。 其他情况dp[i][j]初始为0就行这样递推公式dp[i][j] max(dp[i 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖。
for i in range(len(s)):dp[i][i]1确定遍历顺序 从递推公式dp[i][j] dp[i 1][j - 1] 2 和 dp[i][j] max(dp[i 1][j], dp[i][j - 1]) 可以看出dp[i][j]是依赖于dp[i 1][j - 1] 和 dp[i 1][j] 也就是从矩阵的角度来说dp[i][j] 下一行的数据。 所以遍历i的时候一定要从下到上遍历这样才能保证下一行的数据是经过计算的。 递推公式dp[i][j] dp[i 1][j - 1] 2dp[i][j] max(dp[i 1][j], dp[i][j - 1]) 分别对应着下图中的红色箭头方向如图
for i in range(len(s)-1, -1, -1):for j in range(i1, len(s)):if s[i] s[j]:dp[i][j] dp[i1][j-1] 2else:dp[i][j] max(dp[i1][j], dp[i][j-1])举例推导dp数组 输入s:“cbbd” 为例dp数组状态如图
class Solution:def longestPalindromeSubseq(self, s: str) - int:# dp[i][j]表示从i到j的最长子序列dp [[0]*len(s) for _ in range(len(s))]# 初始化对角线为1for i in range(len(s)):dp[i][i]1# 循环填表,从下到上从左到右for i in range(len(s)-1, -1, -1):for j in range(i1, len(s)):if s[i]s[j]:dp[i][j] dp[i1][j-1] 2else:dp[i][j] max(dp[i1][j], dp[i][j-1])return dp[0][-1]
