一般來說，子串和子數組都是連續的，而子序列是可以不連續的，遇到子序列問題基本上都是用動態規劃求解。

53. 最大子數組和（劍指 Offer 42. 連續子數組的最大和）

class Solution:def maxSubArray(self, nums: List[int]) -> int:n = len(nums)dp = [-10001] * (n+1)dp[0] = nums[0]for i in range(1, n):dp[i] = max(dp[i-1] + nums[i], nums[i])return max(dp)

把 dp 數組定義為：元素 dp[i] 表示以 nums[i] 為結尾的數組的連續子數組最大和。則初始條件為 dp[0] = nums[0] （只有一個元素）。如果知道了 dp[i-1]，則 dp[i] 只有兩種取值：dp[i-1] + nums[i] 和 nums[i]，取兩者中的較大值即可。

152. 乘積最大子數組

class Solution:def maxProduct(self, nums: List[int]) -> int:n = len(nums)if n == 1:return nums[0]max_dp = [0] * nmin_dp = [0] * nmax_dp[0] = min_dp[0] = nums[0]for i in range(1, n):max_dp[i] = max(max_dp[i-1] * nums[i], min_dp[i-1] * nums[i], nums[i])min_dp[i] = min(max_dp[i-1] * nums[i], min_dp[i-1] * nums[i], nums[i])return max(max(max_dp), max(min_dp))

求乘積的話能不能照搬上面的思路呢？是不可以的，因為乘積可能為負數，每次只取較大值的話是不會選擇負數的，但是最大乘積可能由負負得正而來。解決方法是使用兩個 dp 數組，一個記錄最大值一個記錄最小值（負的最大），這樣當第一次出現負數時，結果會被 min_dp 記錄下來，而第二次出現負數的時候，結果又會進入 max_dp。

674. 最長連續遞增序列

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

這題的關鍵詞是連續，所以如果在位置 i 的數字大于前一個數字，就記錄這個位置的序列長度（dp[i]）為前一個位置序列長度加一（ dp[i-1] + 1）

300. 最長遞增子序列

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

將 dp 數組定義為：元素 dp[i] 表示以 nums[i] 為結尾的數組的最長遞增子序列長度。初始化 dp 數組的每個元素都是1（最小都是它本身，長度為1）。當遍歷到 dp[i] 時，它前面的每個 dp[j] （j < i） 我們都是知道的，需要從中找到能構成遞增關系的（nums[i] > nums[j]），最大長度 max(dp[i], dp[j] + 1)。

1143. 最長公共子序列

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:m, n = len(text1), len(text2)dp = [[0 for _ in range(n+1)] for _ in range(m+1)]ans = 0for 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] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])return dp[-1][-1]

dp[i][j]：長度為 [0, i - 1] 的字符串 text1 與長度為 [0, j - 1] 的字符串 text2 的最長公共子序列

如果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] 表示的是長度為 [0, i] 的字符串 text1 與長度為 [0, j] 的字符串 text2 的最長公共子序列，在初始化上就麻煩不少，代碼如下：

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:m, n = len(text1), len(text2)dp = [[0 for _ in range(n)] for _ in range(m)]ans = 0if text1[0] == text2[0]:dp[0][0] = 1for i in range(1, m):if text1[i] == text2[0] or dp[i-1][0] == 1:dp[i][0] = 1for j in range(1, n):if text1[0] == text2[j] or dp[0][j-1] == 1:dp[0][j] = 1for i in range(1, m):for j in range(1, n):if text1[i] == text2[j]: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]

673. 最長遞增子序列的個數

class Solution:def findNumberOfLIS(self, nums: List[int]) -> int:n = len(nums)max_len = ans = 0dp = [1] * ncnt = [1] * nfor i in range(n):for j in range(i):# 如果當前元素可以加入遞增序列，使得dp[j]可以+1if nums[i] > nums[j]:# 遇到更長的遞增子序列，則更新if dp[j] + 1 > dp[i]:dp[i] = dp[j] + 1cnt[i] = cnt[j] # 重置計數# 相同長度的遞增子序列elif dp[j] + 1 == dp[i]:cnt[i] += cnt[j]if dp[i] > max_len:max_len = dp[i]ans = cnt[i] # 重置計數elif dp[i] == max_len:ans += cnt[i]return ans

在上一題的基礎上，要對最長遞增子序列的個數進行計數，我們定義一個 cnt 數組，cnt[i] 表示以 nums[i] 結尾的最長遞增子序列的個數。設 nums 的最長遞增子序列的長度為 maxLen，那么答案 ans 為所有滿足 dp[i] = maxLen 的 i 所對應的 cnt[i] 之和。關鍵是對當前元素可以加入遞增序列（nums[i] > nums[j]）后的情況進行分類討論，以找出當前最長的遞增子序列以及對它進行計數。

354. 俄羅斯套娃信封問題

class Solution:def maxEnvelopes(self, envelopes: List[List[int]]) -> int:envelopes.sort(key=lambda k: (k[0], -k[1]))n = len(envelopes)dp = [1] * nfor i in range(n):for j in range(i):if envelopes[i][1] > envelopes[j][1]:dp[i] = max(dp[i], dp[j] + 1)return max(dp)

關鍵思路是對寬度進行升序排序而對高度進行降序排序，降序的目的是為了保證寬度相同時只有一個信封會被選入到最長遞增子序列當中（如果高度也是升序，則會進入多個，但是它們的寬度相同，不符合題意）。最后求關于高度的最長遞增子序列的長度即為答案。

198. 打家劫舍

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)if n <= 2:return max(nums)dp = [0] * ndp[0] = nums[0]dp[1] = max(nums[0], nums[1])for i in range(2, n):dp[i] = max(dp[i-1], dp[i-2] + nums[i])return dp[-1]

這題可以看作是不相鄰子序列的最大和，dp[i] 表示到第 i 號房為止能偷到的最多錢，狀態轉移方程為偷了第 i - 2 家后再偷第 i 家或者偷了第 i - 1 家（不能偷第 i 家了）兩者的最大值。

740. 刪除并獲得點數

class Solution:def deleteAndEarn(self, nums: List[int]) -> int:# 以數字作為下標，對應點數作為值maxVal = max(nums)total = [0] * (maxVal + 1)for val in nums:total[val] += val# 打家劫舍問題n = len(total)if n == 1:return total[0]dp = [0] * ndp[0] = total[0]dp[1] = max(total[0], total[1])for i in range(2, n):dp[i] = max(dp[i-2] + total[i], dp[i-1])return dp[n-1]

將出現的數字作為下標，數字出現次數 * 數字本身 = 數字對應的點數，點數作為值，構建一個 total 數組，即變成了對于 total 數組的打家劫舍問題。

213. 打家劫舍 II

class Solution:def rob(self, nums: List[int]) -> int:if not nums:return 0n = len(nums)if n == 1:return nums[0]if n == 2:return max(nums)dp_1 = [0] * ndp_2 = [0] * ndp_1[0] = nums[0]dp_1[1] = max(nums[0], nums[1])dp_2[1] = nums[1]dp_2[2] = max(nums[1], nums[2])for i in range(2, n-1):dp_1[i] = max(dp_1[i-2] + nums[i], dp_1[i-1])for i in range(3, n):dp_2[i] = max(dp_2[i-2] + nums[i], dp_2[i-1])return max(dp_1[-2], dp_2[-1])

房屋首尾相連了，意味著偷了第一家就不能偷最后一家，反之亦然。因此，我們可以分類討論，把偷第一家和偷最后一家分別考慮，用兩個 dp 分別算出兩個方案的結果，取較大值即可。對于第一家和最后一家都不偷的情況，其實已經被包含在上面兩種情況里面了，因為上面也只是考慮偷第一家或最后一家，但不一定偷。

337. 打家劫舍 III

class Solution:def rob(self, root: TreeNode) -> int:def postTravel(root):if not root: return 0, 0 # 偷，不偷left = postTravel(root.left)right = postTravel(root.right)# 偷當前節點, 則左右子樹都不能偷val_1 = root.val + left[1] + right[1]# 不偷當前節點, 則取左右子樹中最大的值val_2 = max(left) + max(right)return val_1, val_2return max(postTravel(root))

這題實際上不算子序列問題，而是樹形 dp 問題，但還是打家劫舍系列的所以放一起了。使用的是后序遍歷，因為要先獲得左右子樹的結果，然后對于當前節點，有偷或者不偷兩種方案，都需要返回，取其中的較大值即可，對于左右子樹也是一樣的。

總結

以上是生活随笔為你收集整理的子串、子数组与子序列类型问题的动态规划求解（Leetcode题解-Python语言）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。