题目分类打家劫舍198. 打家劫舍规则相邻房间不能偷当前房间偷不偷取决于前一个房间的状态1dp数组的定义考虑下标i包含i之前的这些房间所能偷的最大的钱币为 dp[i]最终求的即为 dp[nums.size() - 1]2递推公式得到 dp[i] 只有以下两种情况偷i房间也就意味着i-1房间不能偷dp[i-2] nums[i]不偷i房间未必一定偷i-1房间只是考虑到i-1房间的范围了dp[i-1]取两者的最大值3初始化从递推公式可以看出递推的基础是 dp[0] 和 dp[1]dp[0] nums[0]dp[1] max(nums[0], nums[1])其他下标初始成什么值都可以都会被递推公式计算得到的值所覆盖。默认初始为04遍历顺序从递推公式可以看出i状态是由前面两个状态推导而来的因此一定是从小到大遍历for循环的i是从2开始的因为0和1都已经初始化了class Solution: def rob(self, nums: List[int]) - int: # 注意要加特殊情况的判断即只有一个房屋时 # 否则下面dp[1]的那行会报错list index out of range if len(nums) 1: return nums[0] 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[len(nums)-1]213. 打家劫舍II将上题中的线性数组首尾相连、连成环了因此首尾元素最多只能同时选一个情况1首尾都不选。此时跟上一题是一样的情况2考虑首元素不考虑尾元素。此时把去掉尾元素的数组传入上题的函数就可以情况3考虑尾元素不考虑首元素。此时把去掉首元素的数组传入上题的函数就可以其实情况2和3是包含了情况1的所以只要求解情况2和情况3的最优解再取个max即可class Solution: def rob_1(self, nums): if len(nums) 1: return nums[0] 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[len(nums)-1] def rob(self, nums: List[int]) - int: if len(nums) 1: return nums[0] # 取以下两种情况的最大值: # 1. 考虑首元素不考虑尾元素 # 2. 不考虑首元素考虑尾元素 return max(self.rob_1(nums[:len(nums)-1]), self.rob_1(nums[1:]))337. 打家劫舍III【树形dp】337.打家劫舍 III | 树形动态规划 | 后序遍历 | 状态转移 | 代码随想录在一个二叉树中偷钱币规则仍然是相邻节点不能偷只要线连在一起的都算相邻节点如若偷了某节点其左右孩子就不能偷了暴力法超时很多节点会重复运算优化版记忆化递归递归过程中用一个map之类的容器把我们遍历过的节点计算的结果保存一下避免重复地进行运算动态规划1dp数组的定义每个节点只有两个状态偷还是不偷用一个长度为2的一维dp数组就可以表示出来即dp[0]表示不偷当前节点所获得的最大金额dp[1]表示偷~递归遍历二叉树系统栈里会保存每一层递归里的参数每一层递归都会有长度为2的dp数组。因此一层一层往下递归时当前层的dp数组就表示当前这个节点的状态不用再去定义每一个节点的dp数组从底往上遍历后序遍历左右中最后求的即是根节点偷or不偷两种状态取一个max2递归函数的参数和返回值返回值一维的长度为2的dp数组即当前节点偷or不偷的状态所代表的最大金币数量3终止条件当前遍历的值为空返回初始为0的长度为2的数组两个元素都是04遍历顺序偷当前节点所取得的最大钱币当前节点的值 左右孩子一定不能偷取左右孩子的dp[0]不偷当前节点考虑是否要偷左右孩子取决于各自偷or不偷两种状态的最大值# 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: return max(self.traversal(root)) def traversal(self, cur): # 返回值为一个一维的长度为2的dp数组0维表示不偷1维表示偷 # 1. 下标为 0 记录 **不偷该节点** 所得到的的最大金钱 # 2. 下标为 1 记录 **偷该节点** 所得到的的最大金钱 if not cur: return [0, 0] # 左右中后序遍历 left_dp self.traversal(cur.left) right_dp self.traversal(cur.right) # 中 val_no max(left_dp[0], left_dp[1]) max(right_dp[0], right_dp[1]) # 不偷当前节点偷子节点 val_yes cur.val left_dp[0] right_dp[0] # 偷当前节点不偷子节点 return [val_no, val_yes]股票问题I只能买卖一次定义两个状态 —— 持有包含当天买入和保持买入状态和不持有包含当天卖出和保持卖出状态II可以买卖多次也是定义持有和不持有两个状态III至多买卖两次把买卖两次的状态都列出来了一共五个状态IV至多买卖k次相对于至多买卖两次就是把二维的坐标确定的常量数用变量来泛指含冷冻期把具体卖出股票的状态从不持有的状态里单独拆出来了因为冷冻期的前一天是具体卖出股票的操作。一共4个状态0持有1不持有2卖出3冷冻期含手续费和II一样只是多了每买卖就会扣除一次手续费的操作121. 买卖股票的最佳时机I只有一支股票且只买卖一次股票贪心因为股票就买卖一次那么贪心的想法很自然就是取区间的左侧最小值取区间的右侧最大值得到的差值就是最大利润class Solution: def maxProfit(self, prices: List[int]) - int: low_price prices[0] res 0 for i in range(len(prices)): low_price min(low_price, prices[i]) # 取左侧最小价格 res max(res, prices[i]- low_price) # 取最大区间利润 return res时间复杂度O(n)空间复杂度O(1)动态规划二维dp1dp数组的定义dp[i][0] 表示第i天持有股票所得的最多现金dp[i][1] 表示第i天不持有股票所得的最多现金注意这里说的是“持有”“持有”不代表就是当天“买入”也有可能是昨天就“买入”了今天保持“持有”的状态最终求的即是 dp[len-1][1]因为不持有股票状态所得的金钱一定比持有股票状态得到的多2递推公式3初始化4遍历顺序从递推公式可以看出dp[i] 都是由 dp[i - 1] 推导出来的那么一定是从前向后遍历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], -prices[i]) dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i]) return dp[len(prices)-1][1]时间复杂度O(n)空间复杂度O(n)动态规划滚动数组优化可以使用滚动数组来把二维dp的空间复杂度降低到O(1)从递推公式可以看出dp[i] 只依赖于 dp[i - 1] 的状态因此只需要记录当前这一天的dp状态和前一天的dp状态就可以了写法1二维dpclass Solution: def maxProfit(self, prices: List[int]) - int: # 这里只开辟了一个 2 * 2 大小的二维数组 dp [[0, 0] for _ in range(2)] # [持有, 不持有] dp[0][0] -prices[0] dp[0][1] 0 for i in range(1, len(prices)): # 每一个坐标的地方都加上 % 2 dp[i % 2][0] max(dp[(i-1) % 2][0], -prices[i]) dp[i % 2][1] max(dp[(i-1) % 2][1], dp[(i-1) % 2][0] prices[i]) return dp[(len(prices)-1) % 2][1]写法2一维dpclass Solution: def maxProfit(self, prices: List[int]) - int: # 注意这里只维护两个常量因为dp0的更新不受dp1的影响 dp0 -prices[0] # 持有 dp1 0 # 不持有 for i in range(1, len(prices)): dp1 max(dp1, dp0 prices[i]) dp0 max(dp0, -prices[i]) return dp1122. 买卖股票的最佳时机II只有一支股票股票可以买卖多次贪心收割每一天的正利润将每一天的正利润累加就是买卖多次收获的最大利润class Solution: def maxProfit(self, prices: List[int]) - int: res 0 for i in range(1, len(prices)): # 至少要从下标1的位置才能减去昨天的价格才能得到当天的利润 profit prices[i] - prices[i-1] if profit 0: res profit return res动态规划二维dp本题跟上题【121】的区别就是不持有卖出的情况一样持有买入的情况不一样。这是因为本题的股票可以买卖多次所以买入股票的时候可能会有之前买卖股票所得的利润即dp[i - 1][1]所以利润为 dp[i - 1][1] - prices[i]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[len(prices)-1][1]动态规划滚动数组优化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]) return dp1123. 买卖股票的最佳时机III股票至多买卖两次1dp数组的定义显然 dp[i][0] dp[i-1][0] 02递推公式3初始化4遍历顺序从递归公式可以看出一定是从前向后遍历因为 dp[i] 依靠 dp[i - 1] 的数值收获最大利润的时候一定是股票卖出的状态而两次卖出股票的操作中一定是最后一次卖出股票后的现金最多。所以最终可以获得的最大利润是 dp[prices.size() - 1][4]class Solution: def maxProfit(self, prices: List[int]) - int: # [未操作第一次买入第一次卖出第二次买入第二次卖出] dp [[0, 0, 0, 0, 0] 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[len(prices)-1][4]时间复杂度O(n)空间复杂度O(n × 5)优化版只维护第i天和第i-1天这两天的状态即可因为第i天依赖于第i-1天188. 买卖股票的最佳时机IV股票至多买卖k次1dp数组的定义同上题【123题】二维数组 dp[i][j] 第i天的状态为j所剩下的最大现金是dp[i][j]除了0以外偶数就是卖出奇数就是买入j的范围为 2 * k 12递推公式for (int j 0; j 2 * k - 1; j 2) { dp[i][j 1] max(dp[i - 1][j 1], dp[i - 1][j] - prices[i]); // 买 dp[i][j 2] max(dp[i - 1][j 2], dp[i - 1][j 1] prices[i]); // 卖 }第2个维度不能出现固定数字一定用 j 来表示类比j为奇数是买、偶数是卖的状态3初始化dp[0][j] 当j为奇数的时候都初始化为 -prices[0]4遍历顺序一定是从前向后遍历因为dp[i]依靠dp[i - 1]的数值最后一次卖出一定是利润最大的即 dp[prices.size() - 1][2 * k]class Solution: def maxProfit(self, k: int, prices: List[int]) - int: dp [[0] * (2*k1) for _ in range(len(prices))] # 初始化第0天的状态 for j in range(1, 2*k, 2): # 奇数-买入偶数-卖出 dp[0][j] -prices[0] # 奇数 for i in range(1, len(prices)): # i表示天数 for j in range(0, 2*k-1, 2): # j表示状态 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[len(prices)-1][2*k]309. 买卖股票的最佳时机含冷冻期基于122题多次买卖一支股票多加了一个冷冻期卖出股票后的第二天是冷冻期时长一天因为有冷冻期所以在状态拆分的时候一定要把具体卖出股票的状态拆出来因为冷冻期的前一天一定要是具体卖出股票的状态1dp数组的定义定义4个状态0持股状态今天买入或者之前就买入且一直持有1保持卖出两天前卖出且度过了一天冷冻期或者之前就卖出且一直维持卖出状态2今天卖出3冷冻期2递推公式【0持股状态】今天买入或者之前就买入且一直持有【1保持卖出】两天前卖出且度过了一天冷冻期或者之前就卖出且一直维持卖出状态【2今天卖出】【3冷冻期】3初始化4遍历顺序从递归公式上可以看出dp[i] 依赖于 dp[i-1]所以是从前向后遍历最后结果取最后一天状态二三四即1、2、3的maxclass Solution: def maxProfit(self, prices: List[int]) - int: # [持有不持有卖出冷冻期] dp [[0] * 4 for _ in range(len(prices))] dp[0][0] -prices[0] dp[0][1], dp[0][2], dp[0][3] 0, 0, 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][3]-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[len(prices)-1][1], dp[len(prices)-1][2], dp[len(prices)-1][3])时间复杂度O(n)空间复杂度O(n)当然空间复杂度可以优化定义一个dp[2][4]大小的数组就可以了只保存前一天和当前的状态714. 买卖股票的最佳时机含手续费无限次买卖但每次买卖的操作都要支付一笔手续费动态规划相对于【122题】本题只需要在计算卖出操作的时候减去手续费就可以了只有一行代码的diffclass Solution: def maxProfit(self, prices: List[int], fee: 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] - fee) return dp[len(prices)-1][1]贪心class Solution: def maxProfit(self, prices: List[int], fee: int) - int: buy prices[0] res 0 for i in range(len(prices)): if prices[i] buy: buy prices[i] if prices[i] - buy fee: res prices[i] - buy - fee buy prices[i] - fee return res子序列问题不连续300. 最长递增子序列选取一些元素元素要保持递增可以不连续但是必须为这个数组原有的顺序1dp数组的定义以nums[i]为结尾的最长递增子序列的长度为dp[i]2递推公式位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列1的最大值if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1)注意这里不是要将 dp[i] 与 dp[j] 1 进行比较而是要取 dp[j] 1 的最大值3初始化每一个i对应的dp[i]即最长递增子序列的长度起始大小至少都是14遍历顺序遍历i一定是从前向后外层for循环j其实就是遍历0到i-1那么是从前到后还是从后到前遍历都无所谓只要把 0 到 i-1 的元素都遍历了就行内层for循环最终的结果遍历一遍以每一个 nums[i] 为结尾的最长递增子序列的长度然后去求一个maxclass Solution: def lengthOfLIS(self, nums: List[int]) - int: if len(nums) 1: return 1 dp [1] * len(nums) res 0 for i in range(1, len(nums)): for j in range(0, i): # 0 ~ i-1 if nums[j] nums[i]: dp[i] max(dp[i], dp[j]1) res max(res, dp[i]) return res1143. 最长公共子序列相比【718. 最长重复子数组】本题元素之间可以不连续只要保持相对顺序即可1dp数组的定义比较两个数组相等的情况要定义一个二维dp数组长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]为什么不是定义为[0, i]同【718题】是为了精简初始化2递推公式如果text1[i - 1] 与 text2[j - 1]相同那么找到了一个公共元素所以dp[i][j] dp[i - 1][j - 1] 1如果text1[i - 1] 与 text2[j - 1]不相同那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列取最大的即dp[i][j] max(dp[i - 1][j], dp[i][j - 1])3初始化dp[i][0] 0、dp[0][j] 0其他下标都是随着递推公式逐步覆盖初始为多少都可以那么就统一初始为04遍历顺序从前向后从上到下遍历dp[text1.size()][text2.size()] 为最终结果class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: m, n len(text1), len(text2) dp [[0] * (n1) for _ in range(m1)] for i in range(1, m1): for j in range(1, n1): if text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i][j-1], dp[i-1][j]) return dp[m][n]1035. 不相交的线跟【1143. 最长公共子序列】一模一样class Solution: def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) - int: m, n len(nums1), len(nums2) dp [[0] * (n1) for _ in range(m1)] res 0 for i in range(1, m1): for j in range(1, n1): if nums1[i-1] nums2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i][j-1], dp[i-1][j]) res max(res, dp[i][j]) return res连续674. 最长连续递增序列动态规划相比【300. 最长递增子序列】本题多了连续的要求1dp数组的定义以nums[i]为结尾的最长连续递增子序列的长度为dp[i]一定是以下标i为结尾并不是说一定以下标0为起始位置2递推公式3初始化每一个i对应的dp[i]即连续递增子序列的长度起始大小至少都是14遍历顺序从前向后遍历最终结果取 dp[i] 的最大值class Solution: def findLengthOfLCIS(self, nums: List[int]) - int: dp [1] * len(nums) res 1 # 初始化为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时间复杂度O(n)空间复杂度O(n)不连续递增子序列与前0~i个状态有关连续递增子序列只与前一个状态有关贪心class Solution: def findLengthOfLCIS(self, nums: List[int]) - int: res 1 # 连续子序列的最小值是1 cnt 1 for i in range(1, len(nums)): if nums[i] nums[i-1]: cnt 1 # 连续记录 else: cnt 1 # 不连续从1重新开始计数 res max(res, cnt) return res时间复杂度O(n)空间复杂度O(1)718. 最长重复子数组子数组 连续子序列dp[i][j]表示以下标i-1和j-1结尾1dp数组的定义dp[i][j]以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组的长度为dp[i][j]特别注意“以下标i - 1为结尾的A” 指以A[i-1]为结尾的字符串因此在遍历dp[i][j]的时候 i 和 j 都要从1开始2递推公式dp[i][j] 的状态只能由dp[i - 1][j - 1]推导出来当A[i - 1] 和B[j - 1]相等的时候dp[i][j] dp[i - 1][j - 1] 13初始化根据dp[i][j]的定义dp[i][0] 和 dp[0][j] 其实都是没有意义的只是为了方便推导递推公式将它们初始化为0举个例子A[0]如果和B[0]相同的话则dp[1][1] dp[0][0] 1只有dp[0][0]初始为0才符合递推公式的推导逻辑4遍历顺序从前向后遍历先遍历A还是B都可以同时题目要求长度最长的子数组的长度所以在遍历的时候顺便把dp[i][j]的最大值记录下来最终结果把二维dp数组全都遍历一遍找出以每一个元素为结尾的两个字符串进行比较的最长重复子数组然后找出最长的class Solution: def findLength(self, nums1: List[int], nums2: List[int]) - int: dp [[0] * (len(nums2)1) for _ in range(len(nums1)1)] res 0 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] 1 res max(res, dp[i][j]) return res时间复杂度O(n × m)n为A数组的长度m为B数组的长度空间复杂度O(n × m)这里可以做状态压缩即滚动数组具体参考718. 最长重复子数组 | 动态规划 | 滚动数组 | 状态转移 | 代码随想录dp[i][j]表示以下标i和j结尾这样定义初始化要复杂一些dp[i][0] 表示第一个数组和第二个数组中的第一个元素的最长重复子数组也就是拿第一个数组中的每个元素和第二个数组中的第一个元素进行比较如果相等对应位置赋1class Solution: def findLength(self, nums1: List[int], nums2: List[int]) - int: dp [[0] * len(nums2) for _ in range(len(nums1))] res 0 # 初始化 for i in range(len(nums1)): if nums1[i] nums2[0]: dp[i][0] 1 res max(res, 1) for j in range(len(nums2)): if nums1[0] nums2[j]: dp[0][j] 1 res max(res, 1) for i in range(1, len(nums1)): for j in range(1, len(nums2)): if nums1[i] nums2[j]: dp[i][j] dp[i-1][j-1] 1 res max(res, dp[i][j]) return res53. 最大子数组和子数组连续子序列的最大和贪心class Solution: def maxSubArray(self, nums: List[int]) - int: sub_sum 0 res float(-inf) for i in range(len(nums)): sub_sum nums[i] res max(res, sub_sum) # 取区间累计的最大值相当于不断确定最大子序列的终止位置 # 相当于重置最大子序列的起始位置因为遇到负数一定降低了总和 if sub_sum 0: sub_sum 0 return res动态规划1dp数组的定义dp[i]包括下标i以nums[i]为结尾的最大连续子序列和为dp[i]2递推公式3初始化从递推公式可以看出dp[i]依赖于dp[i - 1]的状态dp[0]就是递推公式的基础dp[0] nums[0]4遍历顺序从前向后要找最大的连续子序列就应该找每一个i为终点的连续最大子序列而非dp[nums.size() - 1]class Solution: def maxSubArray(self, nums: List[int]) - int: dp [0] * len(nums) dp[0] nums[0] res nums[0] for i in range(1, len(nums)): dp[i] max(dp[i-1] nums[i], nums[i]) res max(res, dp[i]) return res注意res不能初始化为0需要注意两种情况当数组中所有子数组的和都小于0当第一个数作为子数组的时候是最大和且不为0编辑距离392. 判断子序列编辑距离的入门题从题意中可以看出只需要考虑删除字符串的情况不用考虑增加和替换字符串的情况双指针写法1class Solution: def isSubsequence(self, s: str, t: str) - bool: i, j 0, 0 for j in range(len(t)): if i len(s) and s[i] t[j]: i 1 if i len(s): return True else: return False写法2class Solution: def isSubsequence(self, s: str, t: str) - bool: i, j 0, 0 while i len(s) and j len(t): if s[i] t[j]: i 1 j 1 return i len(s)动态规划跟【1143. 最长公共子序列】非常类似如果s是t的子序列那么最长公共子序列的长度就是len(s)本题只考虑t里删元素【1143题】s和t里都可以删元素1dp数组的定义dp[i][j] 表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度如果定义的dp[i][j]是以下标i为结尾的字符串s和以下标j为结尾的字符串t初始化就比较麻烦了2递推公式3初始化从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]所以dp[0][0]和dp[i][0]是一定要初始化的全部初始化为0即可4遍历顺序从上到下从左到右如果 dp[s.size()][t.size()] 与字符串s的长度相同说明s与t的最长相同子序列就是s那么s就是t的子序列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] 1 else: dp[i][j] dp[i][j-1] return dp[len(s)][len(t)] len(s)115. 不同的子序列不连续这道题目如果不是子序列而是要求连续序列那就可以考虑用KMP构造next数组参考 28. 找出字符串中第一个匹配项的下标、【chap6-字符串】用Python3刷《代码随想录》s字符串中有多少种删除元素的方式使s可以变成t1dp数组的定义dp[i][j] 表示以i-1为结尾的s子序列中出现以j-1为结尾的t的个数2递推公式if (s[i - 1] t[j - 1]) { dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]; } else { dp[i][j] dp[i - 1][j]; }3初始化vectorvectoruint64_t dp(s.size() 1, vectoruint64_t(t.size() 1)); for (int i 0; i s.size(); i) dp[i][0] 1; for (int j 1; j t.size(); j) dp[0][j] 0; // 其实这行代码可以和dp数组初始化的时候放在一起但我为了凸显初始化的逻辑所以还是加上了4遍历顺序dp[i][j]都是根据左上方和正上方推出来的从上到下、从左到右最终求的即是 dp[s.size()][t.size()]class Solution: def numDistinct(self, s: str, t: str) - int: dp [[0] * (len(t)1) for _ in range(len(s)1)] # dp[i][0] for i in range(len(s)1): dp[i][0] 1 # dp[0][j] for j in range(len(t)1): dp[0][j] 0 # dp[0][0] dp[0][0] 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] dp[i-1][j] else: dp[i][j] dp[i-1][j] return dp[len(s)][len(t)]583. 两个字符串的删除操作本题和【115. 不同的子序列】相比两个字符串都可以删除1dp数组的定义dp[i][j]以i-1为结尾的字符串word1和以j-1为结尾的字符串word2想要两个字符串相同所需要删除元素的最少次数2递推公式3初始化4遍历顺序从上到下从左到右最终求的即是 dp[word1.size()][word2.size()]class Solution: def minDistance(self, word1: str, word2: str) - int: m, n len(word1), len(word2) dp [[0] * (n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): 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) # 可简化为 dp[i][j] min(dp[i-1][j]1, dp[i][j-1]1) return dp[m][n]另一种思路等价于求两个字符串的最长公共子序列把最长公共子序列以外的元素都删了即可即word1.size word2.size - 2 × len(最长公共子序列)class Solution: def minDistance(self, word1: str, word2: str) - int: m, n len(word1), len(word2) dp [[0] * (n1) for _ in range(m1)] res 0 for i in range(1, m1): for j in range(1, n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i][j-1], dp[i-1][j]) res max(res, dp[i][j]) return m n - 2 * res # 或者不需要res直接返回dp[m][n] class Solution: def minDistance(self, word1: str, word2: str) - int: m, n len(word1), len(word2) dp [[0] * (n1) for _ in range(m1)] for i in range(1, m1): for j in range(1, n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i][j-1], dp[i-1][j]) return m n - 2 * dp[m][n]72. 编辑距离未必都操作word1两个word都操作也可以1dp数组的定义dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2的最近编辑距离为 dp[i][j]2递推公式if (word1[i - 1] word2[j - 1]) // 不操作 if (word1[i - 1] ! word2[j - 1]) // 增 // 删 // 换 if (word1[i - 1] word2[j - 1]) { dp[i][j] dp[i - 1][j - 1]; } else { // word1 删除一个元素 - dp[i - 1][j] 1 // word2 删除一个元素 - dp[i][j - 1] 1 (word2添加一个元素就相当于word1删除一个元素) // 替换元素 - dp[i - 1][j - 1] 1 (word1替换word1[i-1]使其与word2[j-1]相同此时不用增加元素那么dp[i][j]就是以下标i-2为结尾的word1与以下标j-2为结尾的word2的最近编辑距离一个替换元素的操作) dp[i][j] min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) 1; }3初始化dp[i][0]以下标i-1为结尾的字符串word1和空字符串word2的最近编辑距离为dp[i][0]那么dp[i][0]就应该是i对word1里的元素全部做删除操作即dp[i][0] i;同理dp[0][j] j;4遍历顺序从左到右、从上到下去遍历最终求的即是 dp[word1.size()][word2.size()]class Solution: def minDistance(self, word1: str, word2: str) - int: m, n len(word1), len(word2) dp [[0] * (n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1 return dp[m][n]回文区间dp647. 回文子串连续动态规划1dp数组的定义布尔类型的dp[i][j]表示区间范围 [i, j] 注意是左闭右闭的子串是否是回文子串如果是则 dp[i][j] 为true否则为false2递推公式if (s[i] s[j]) { if (j - i 1) { // 情况一 和 情况二 result; dp[i][j] true; } else if (dp[i 1][j - 1]) { // 情况三 result; dp[i][j] true; } }3初始化若初始化为True表示子串默认都是回文子串这当然不对因此初始化为False4遍历顺序for (int i s.size() - 1; i 0; i--) { // 注意遍历顺序 for (int j i; j s.size(); j) { ... // 递推公式 } }根据dp[i][j]的定义j一定是大于等于i的那么在填充dp[i][j]的时候一定是只填充右上半部分class Solution: def countSubstrings(self, s: str) - int: # [i, j] dp [[False] * len(s) for _ in range(len(s))] res 0 for i in range(len(s)-1, -1, -1): for j in range(i, len(s)): if s[i] s[j]: if i j: dp[i][j] True res 1 elif j - i 1: # 这里可以合并为 j - i 1 dp[i][j] True res 1 elif j - i 1 and dp[i1][j-1] True: dp[i][j] True res 1 return res时间复杂度O(n^2)空间复杂度O(n^2)偏高双指针首先确定回文串就是找对称中心然后向两边扩散看是不是对称的就可以了在遍历中心点的时候要注意中心点有两种情况一个元素可以作为中心点两个元素也可以作为中心点三个元素就可以由一个元素左右添加元素得到四个元素则可以由两个元素左右添加元素得到所以我们在计算的时候要注意一个元素为中心点和两个元素为中心点的情况class Solution: def countSubstrings(self, s: str) - int: res 0 for i in range(len(s)): res self.extend(s, i, i, len(s)) # 以i为中心点 res self.extend(s, i, i1, len(s)) # 以i和i1为中心点 return res def extend(self, s, i, j, n): res 0 while i 0 and j n and s[i] s[j]: # 向左右两边扩散 i - 1 j 1 res 1 return res时间复杂度O(n^2)空间复杂度O(1)516. 最长回文子序列不连续【647. 回文子串】要求连续而本题可以不连续1dp数组的定义dp[i][j]字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]2递推公式在判断回文子串的题目中关键逻辑就是看s[i]与s[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[i]的回文子序列长度为dp[i][j - 1]加入s[j]的回文子序列长度为dp[i 1][j]dp[i][j]一定是取最大的即dp[i][j] max(dp[i 1][j], dp[i][j - 1])if (s[i] s[j]) { dp[i][j] dp[i 1][j - 1] 2; } else { dp[i][j] max(dp[i 1][j], dp[i][j - 1]); }3初始化递推公式计算不到 i 和 j 相同的情况首先要考虑当 i 和 j 相同的情况此时dp[i][j]一定是等于1的即一个字符的回文子序列长度就是1其他情况初始为0就行这样递推公式dp[i][j] max(dp[i 1][j], dp[i][j - 1]) 中的 dp[i][j] 才不会被初始值覆盖4遍历顺序从矩阵的角度来说dp[i][j] 是由下一行的数据推导出来的。所以遍历i的时候一定要从下到上遍历这样才能保证下一行的数据是经过计算的j的话可以正常从左向右遍历dp[0][s.size() - 1] 为最终结果class Solution: def longestPalindromeSubseq(self, s: str) - int: # [i, j] dp [[0] * len(s) for _ in range(len(s))] # 初始化 for i in range(len(s)): dp[i][i] 1 # 单个字符一定是回文的即 j i for i in range(len(s)-1, -1, -1): for j in range(i1, len(s)): # j i if s[i] s[j]: dp[i][j] dp[i1][j-1] 2 else: dp[i][j] max(dp[i1][j], dp[i][j-1]) return dp[0][len(s)-1]时间复杂度: O(n^2)空间复杂度: O(n^2)