动态规划四题精解：从LCS到最大子数组和

1. 动态规划经典四连击：从公共子序列到最大子数组

今天要一口气解决LeetCode上四道经典的动态规划问题：1143最长公共子序列、1035不相交的线、53最大子数组和以及392判断子序列。这四道题看似独立，实则暗藏联系，都是动态规划思想在不同场景下的经典应用。我在刷题过程中发现，很多同学对这类问题的状态转移方程推导存在困惑，下面就用最直白的语言拆解每个问题的解题思路。

2. LeetCode 1143. 最长公共子序列（LCS）

2.1 问题本质剖析

给定两个字符串text1和text2，返回它们的最长公共子序列长度。子序列不要求连续，但相对顺序必须保持一致。例如：

text1 = "abcde", text2 = "ace" LCS = "ace"（长度3）

2.2 动态规划解法详解

定义dp[i][j]表示text1前i个字符和text2前j个字符的LCS长度。状态转移分两种情况：

1. 当text1[i-1] == text2[j-1]时：

   dp[i][j] = dp[i-1][j-1] + 1

2. 当字符不等时：

   dp[i][j] = max(dp[i-1][j], dp[i][j-1])

完整代码实现：

def longestCommonSubsequence(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-1][j], dp[i][j-1]) return dp[m][n]

2.3 空间优化技巧

实际可以优化到O(min(m,n))空间，使用滚动数组：

def longestCommonSubsequence(text1: str, text2: str) -> int: if len(text1) < len(text2): text1, text2 = text2, text1 # 确保text2是较短的 m, n = len(text1), len(text2) prev = [0]*(n+1) curr = [0]*(n+1) for i in range(1, m+1): for j in range(1, n+1): if text1[i-1] == text2[j-1]: curr[j] = prev[j-1] + 1 else: curr[j] = max(prev[j], curr[j-1]) prev, curr = curr, prev return prev[n]

3. LeetCode 1035. 不相交的线

3.1 问题转化艺术

在两条平行线上绘制连接相同数字的直线，要求直线不相交。这实际上就是求两个数组的最长公共子序列！因为连线顺序必须保持一致，且不能交叉。

示例：

nums1 = [1,4,2], nums2 = [1,2,4] 最大连线数 = 2（连接1-1和4-4 或 1-1和2-2）

3.2 代码实现

直接复用LCS的解法：

def maxUncrossedLines(nums1: List[int], nums2: List[int]) -> int: return longestCommonSubsequence(nums1, nums2)

注意：虽然参数类型从字符串变成了数组，但解法完全一致。这是算法问题中常见的"换汤不换药"现象。

4. LeetCode 53. 最大子数组和

4.1 问题重述

找出一个整数数组中具有最大和的连续子数组。例如：

nums = [-2,1,-3,4,-1,2,1,-5,4] 连续子数组 [4,-1,2,1] 的和最大为6

4.2 动态规划解法

定义dp[i]表示以nums[i]结尾的最大子数组和。状态转移方程：

dp[i] = max(nums[i], dp[i-1] + nums[i])

优化空间后的实现：

def maxSubArray(nums: List[int]) -> int: max_sum = curr_sum = nums[0] for num in nums[1:]: curr_sum = max(num, curr_sum + num) max_sum = max(max_sum, curr_sum) return max_sum

4.3 分治法拓展

虽然DP是更优解，但了解分治法也有助于理解问题本质：

def maxSubArray(nums: List[int]) -> int: def divide_conquer(l, r): if l == r: return nums[l] mid = (l + r) // 2 left = divide_conquer(l, mid) right = divide_conquer(mid+1, r) # 计算跨越中点的最大和 left_max = curr = nums[mid] for i in range(mid-1, l-1, -1): curr += nums[i] left_max = max(left_max, curr) right_max = curr = nums[mid+1] for i in range(mid+2, r+1): curr += nums[i] right_max = max(right_max, curr) cross = left_max + right_max return max(left, right, cross) return divide_conquer(0, len(nums)-1)

5. LeetCode 392. 判断子序列

5.1 问题描述

判断字符串s是否是字符串t的子序列（可以不连续但顺序一致）。例如：

s = "abc", t = "ahbgdc" → True s = "axc", t = "ahbgdc" → False

5.2 双指针解法

最直观的解法，时间复杂度O(n)：

def isSubsequence(s: str, t: str) -> bool: i = j = 0 while i < len(s) and j < len(t): if s[i] == t[j]: i += 1 j += 1 return i == len(s)

5.3 动态规划预处理

对于需要多次检查不同s的情况，可以预处理t：

def isSubsequence(s: str, t: str) -> bool: # 预处理t，建立字符到位置列表的映射 from collections import defaultdict import bisect char_indices = defaultdict(list) for idx, char in enumerate(t): char_indices[char].append(idx) # 检查s prev = -1 for char in s: if char not in char_indices: return False # 在char_indices[char]中找到第一个大于prev的索引 indices = char_indices[char] i = bisect.bisect_right(indices, prev) if i == len(indices): return False prev = indices[i] return True

6. 四题对比与经验总结

6.1 动态规划解题框架

1. 定义dp数组含义
2. 确定初始条件
3. 推导状态转移方程
4. 考虑空间优化可能

6.2 常见错误排查

• 数组越界：注意dp数组大小通常为n+1
• 初始化错误：特别是dp[0][0]或dp[0]的初始值
• 状态转移条件混淆：特别是字符比较时的索引偏移

6.3 性能优化技巧

6.4 刷题进阶建议

1. 先手写状态转移表帮助理解
2. 对每道题至少尝试两种解法
3. 整理相似题目对比记忆（如LCS与编辑距离）
4. 定期复习经典题目的变形

我在实际刷题中发现，很多动态规划问题都有相似的解题模式。掌握这四道题后，可以尝试挑战更难的问题如：

• 72. 编辑距离
• 115. 不同的子序列
• 583. 两个字符串的删除操作

最后分享一个调试技巧：当状态转移方程不确定时，可以打印出完整的dp表格，对照示例手动验证每个状态的正确性。这个方法帮我找出了不少边界条件的错误。