当前位置：首页 > news >正文

【chap11-动态规划（下 - 打家劫舍股票问题子序列问题）】用Python3刷《代码随想录》

news 2026/8/5 1:31:24

题目分类

打家劫舍

198. 打家劫舍

规则：相邻房间不能偷

当前房间偷不偷取决于前一个房间的状态

（1）dp数组的定义

考虑下标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])
其他下标：初始成什么值都可以，都会被递推公式计算得到的值所覆盖。默认初始为0

（4）遍历顺序

从递推公式可以看出，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之类的容器，把我们遍历过的节点计算的结果保存一下，避免重复地进行运算）

动态规划：

（1）dp数组的定义

每个节点只有两个状态：偷还是不偷
用一个长度为2的一维dp数组就可以表示出来，即dp[0]表示不偷当前节点所获得的最大金额，dp[1]表示偷~
递归遍历二叉树，系统栈里会保存每一层递归里的参数，每一层递归都会有长度为2的dp数组。因此一层一层往下递归时，当前层的dp数组就表示当前这个节点的状态，不用再去定义每一个节点的dp数组
从底往上遍历（后序遍历），左右中
最后求的即是根节点偷or不偷两种状态，取一个max

（2）递归函数的参数和返回值

返回值：一维的长度为2的dp数组，即当前节点偷or不偷的状态，所代表的最大金币数量

（3）终止条件：当前遍历的值为空，返回初始为0的长度为2的数组（两个元素都是0）

（4）遍历顺序

偷当前节点所取得的最大钱币：当前节点的值 + 左右孩子一定不能偷（取左右孩子的dp[0]）
不偷当前节点：考虑是否要偷左右孩子，取决于各自偷or不偷两种状态的最大值

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def rob(self, root: Optional[TreeNode]) -> int: 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)

动态规划（二维dp）

（1）dp数组的定义

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：二维dp

class 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：一维dp

class 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 dp1

122. 买卖股票的最佳时机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 dp1

123. 买卖股票的最佳时机III

股票至多买卖两次

（1）dp数组的定义

显然 dp[i][0] = dp[i-1][0] = 0

（2）递推公式

（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次

（1）dp数组的定义

同上题【123题】，二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]
除了0以外，偶数就是卖出，奇数就是买入
j的范围为 2 * k + 1

（2）递推公式

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*k+1) 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][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]) # 卖出 return dp[len(prices)-1][2*k]

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

基于122题（多次买卖一支股票）多加了一个冷冻期，卖出股票后的第二天是冷冻期（时长一天）

因为有冷冻期，所以在状态拆分的时候，一定要把具体卖出股票的状态拆出来，因为冷冻期的前一天一定要是具体卖出股票的状态

（1）dp数组的定义

定义4个状态
0：持股状态（今天买入，或者之前就买入且一直持有）
1：保持卖出（两天前卖出且度过了一天冷冻期，或者之前就卖出且一直维持卖出状态）
2：今天卖出
3：冷冻期

（2）递推公式

【0：持股状态】今天买入，或者之前就买入且一直持有

【1：保持卖出】两天前卖出且度过了一天冷冻期，或者之前就卖出且一直维持卖出状态

【2：今天卖出】

【3：冷冻期】

（3）初始化

（4）遍历顺序

从递归公式上可以看出，dp[i] 依赖于 dp[i-1]，所以是从前向后遍历
最后结果取最后一天状态二三四（即1、2、3）的max

class 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题】，本题只需要在计算卖出操作的时候减去手续费就可以了，只有一行代码的diff

class 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. 最长递增子序列

选取一些元素，元素要保持递增，可以不连续，但是必须为这个数组原有的顺序

（1）dp数组的定义

以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]（即最长递增子序列的长度）起始大小至少都是1

（4）遍历顺序

遍历i一定是从前向后（外层for循环）
j其实就是遍历0到i-1，那么是从前到后，还是从后到前遍历都无所谓，只要把 0 到 i-1 的元素都遍历了就行（内层for循环）

最终的结果：遍历一遍以每一个 nums[i] 为结尾的最长递增子序列的长度，然后去求一个max

class 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 res

1143. 最长公共子序列

相比【718. 最长重复子数组】，本题元素之间可以不连续，只要保持相对顺序即可

（1）dp数组的定义

比较两个数组相等的情况，要定义一个二维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
其他下标都是随着递推公式逐步覆盖，初始为多少都可以
那么就统一初始为0

（4）遍历顺序

从前向后，从上到下遍历
dp[text1.size()][text2.size()] 为最终结果

class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [[0] * (n+1) for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): 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] * (n+1) for _ in range(m+1)] res = 0 for i in range(1, m+1): for j in range(1, n+1): 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. 最长递增子序列】，本题多了连续的要求

（1）dp数组的定义

以nums[i]为结尾的最长连续递增子序列的长度为dp[i]
一定是以下标i为结尾，并不是说一定以下标0为起始位置

（2）递推公式

（3）初始化

每一个i对应的dp[i]（即连续递增子序列的长度）起始大小至少都是1

（4）遍历顺序

从前向后遍历

最终结果取 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结尾

（1）dp数组的定义

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] + 1

（3）初始化

根据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] 表示第一个数组和第二个数组中的第一个元素的最长重复子数组，也就是拿第一个数组中的每个元素和第二个数组中的第一个元素进行比较，如果相等，对应位置赋1

class 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 res

53. 最大子数组和

子数组（连续子序列）的最大和

贪心

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

动态规划

（1）dp数组的定义

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. 判断子序列

编辑距离的入门题，从题意中可以看出，只需要考虑删除字符串的情况，不用考虑增加和替换字符串的情况

双指针

写法1：

class 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

写法2：

class 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里都可以删元素

（1）dp数组的定义

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可以变成t

（1）dp数组的定义

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）初始化

vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_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. 不同的子序列】相比，两个字符串都可以删除

（1）dp数组的定义

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] * (n+1) for _ in range(m+1)] for i in range(m+1): dp[i][0] = i for j in range(n+1): dp[0][j] = j for i in range(1, m+1): for j in range(1, n+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) # 可简化为 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] * (n+1) for _ in range(m+1)] res = 0 for i in range(1, m+1): for j in range(1, n+1): 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] * (n+1) for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): 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都操作也可以

（1）dp数组的定义

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] * (n+1) for _ in range(m+1)] for i in range(m+1): dp[i][0] = i for j in range(n+1): dp[0][j] = j for i in range(1, m+1): for j in range(1, n+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], dp[i][j-1], dp[i-1][j-1]) + 1 return dp[m][n]

回文（区间dp）

647. 回文子串（连续）

动态规划

（1）dp数组的定义

布尔类型的dp[i][j]：表示区间范围 [i, j] （注意是左闭右闭）的子串是否是回文子串，如果是，则 dp[i][j] 为true，否则为false

（2）递推公式

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，表示子串默认都是回文子串，这当然不对
因此初始化为False

（4）遍历顺序

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[i+1][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, i+1, len(s)) # 以i和i+1为中心点 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. 回文子串】要求连续，而本题可以不连续

（1）dp数组的定义

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(i+1, len(s)): # j > i 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]) return dp[0][len(s)-1]

时间复杂度: O(n^2)
空间复杂度: O(n^2)

查看全文

http://www.cnnetsun.cn/news/1738123.html