代码随想录第36天：动态规划9（序列问题）
一、最长递增子序列（Leetcode 300）
1.dp数组定义：
dp[i] 为以 nums[i] 结尾的最长递增子序列长度。
2.状态转移：
dp[i] = max(dp[i], dp[j] + 1) for all j < i and nums[j] < nums[i]
2.dp数组初始化：
所有 dp[i] = 1，每个元素自身构成一个序列。
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:n = len(nums)if n == 0:return 0# 初始化 dp 数组，dp[i] 表示以 nums[i] 结尾的最长递增子序列长度dp = [1] * n # 每个元素自身至少是一个长度为1的递增子序列# 遍历所有元素，尝试更新 dp[i]for i in range(n):for j in range(i):# 如果前一个元素小于当前元素，说明可以递增if nums[j] < nums[i]:# 更新 dp[i]：取之前小于它的元素能形成的最长递增子序列 +1dp[i] = max(dp[i], dp[j] + 1)# 最终答案是 dp 数组中的最大值return max(dp)
二、最长连续递增序列（Leetcode 674）
相比题一多了要求“连续”
1.dp数组定义：
dp[i] 为以 nums[i] 结尾的最长递增子序列长度。
2.状态转移：
dp[i] = max(dp[i], dp[j] + 1) for all j < i and nums[j] < nums[i]
2.dp数组初始化：
所有 dp[i] = 1，每个元素自身构成一个序列。
class Solution:def findLengthOfLCIS(self, nums: List[int]) -> int:n = len(nums)if n <= 1:return 1dp = [1] * n # 初始化：每个位置至少是1max_len = 1 # 用于记录最大值for i in range(1, n):if nums[i] > nums[i - 1]:dp[i] = dp[i - 1] + 1else:dp[i] = 1max_len = max(max_len, dp[i]) # 更新最大长度return max_len
三、最长重复子数组 （Leetcode 718）
1.dp数组及下标定义
dp[i][j] 表示：以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度。
2.状态转移方程：
-
若
nums1[i-1] == nums2[j-1]：
dp[i][j] = dp[i-1][j-1] + 1 -
否则：
dp[i][j] = 0（连续子数组中断）
3.dp数组初始化：
根据dp[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！
但dp[i][0] 和dp[0][j]要初始值，为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1
所以dp[i][0] 和dp[0][j]初始化为0。
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) -> int:n, m = len(nums1), len(nums2)# 初始化 dp 数组，dp[i][j] 表示 nums1 前 i 个元素与 nums2 前 j 个元素# 的最长公共子数组（结尾必须是 nums1[i-1] 与 nums2[j-1]）的长度dp = [[0] * (m + 1) for _ in range(n + 1)]max_len = 0 # 记录最长公共子数组的长度# 遍历 nums1 和 nums2 所有元素for i in range(1, n + 1):for j in range(1, m + 1):# 如果当前两个元素相等，更新 dp 值if nums1[i - 1] == nums2[j - 1]:# 在两个前缀都减 1 的基础上加 1dp[i][j] = dp[i - 1][j - 1] + 1# 更新最大长度max_len = max(max_len, dp[i][j])# 否则默认 dp[i][j] = 0（初始化时已经为 0）return max_len
4.dp数组初始化注意事项：
dp = [[0] * (列数) for _ in range(行数)]
那么你的外层循环必须是 for i in range(行数 - 1)，
内层循环是 for j in range(列数 - 1)，并且数组元素访问要对应上。
四、最长公共子序列 （Leetcode 1143）
1.dp数组定义：
dp[i][j] 表示：text1 的前 i 个字符 和 text2 的前 j 个字符 的最长公共子序列长度
2.状态转移：
如果 text1[i - 1] == text2[j - 1]，说明当前字符可以匹配：
dp[i][j] = dp[i - 1][j - 1] + 1
否则假设在比较字符串 text1[0..i-1] 和 text2[0..j-1]：
-
当前字符不匹配：
text1[i - 1] != text2[j - 1]
这意味着：我们无法把这两个字符都纳入公共子序列中。
我们有两个选择：
-
跳过 text1[i - 1]，继续比较前 i-1 个字符与前 j 个字符
-
即：
dp[i - 1][j]
-
-
跳过 text2[j - 1]，继续比较前 i 个字符与前 j-1 个字符
-
即：
dp[i][j - 1]
-
我们选择其中 能构成更长公共子序列的路径，所以取最大值：
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
2.dp数组初始化：
dp[0][*] 和 dp[*][0] = 0，表示有一个空串时，LCS 为 0
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:m, n = len(text1), len(text2)# 创建 dp 数组，额外多一行一列用于处理边界dp = [[0] * (n + 1) for _ in range(m + 1)]# 遍历每个字符for i in range(1, m + 1):for j in range(1, n + 1):# 如果当前字符相同，匹配成功，继承左上角 +1if 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[m][n]