动态规划经典问题解析：最长公共子序列与最大子数组和

发布时间：2026/10/27 6:14:20
动态规划经典问题解析：最长公共子序列与最大子数组和

1. 动态规划经典问题实战解析

今天我想和大家分享LeetCode上四个经典的动态规划问题：1143.最长公共子序列、1035.不相交的线、53.最大子数组和以及392.判断子序列。这几个问题看似不同，实则都体现了动态规划的核心思想，非常适合用来训练DP思维。

2. LeetCode 1143. 最长公共子序列

2.1 问题描述与理解

给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。子序列是指在不改变字符相对顺序的情况下删除某些字符（也可以不删除）后组成的新字符串。

例如： text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，长度为3。

2.2 DP状态定义与转移方程

我们定义dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度。

状态转移方程：

  • 当text1[i-1] == text2[j-1]时：dp[i][j] = dp[i-1][j-1] + 1
  • 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

2.3 代码实现

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.4 空间优化技巧

可以将二维DP优化为一维数组，空间复杂度从O(mn)降为O(n)：

def longestCommonSubsequence(text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [0]*(n+1) for i in range(1, m+1): prev = 0 for j in range(1, n+1): temp = dp[j] if text1[i-1] == text2[j-1]: dp[j] = prev + 1 else: dp[j] = max(dp[j], dp[j-1]) prev = temp return dp[n]

3. LeetCode 1035. 不相交的线

3.1 问题转化

这道题看似是几何问题，实际上可以转化为最长公共子序列问题。在数组A和B中绘制不相交的连线，等价于找到A和B的最长公共子序列。

3.2 解法分析

因为连线不能相交，所以必须保持相对顺序，这与LCS的定义完全一致。因此可以直接复用1143题的解法。

3.3 代码实现

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

4. LeetCode 53. 最大子数组和

4.1 问题描述

给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为6。

4.2 动态规划解法

定义dp[i]为以nums[i]结尾的最大子数组和：

  • dp[i] = max(nums[i], dp[i-1]+nums[i])
  • 最终结果是max(dp)

4.3 代码实现

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

4.4 空间优化

可以只用一个变量记录前一个状态：

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

5. LeetCode 392. 判断子序列

5.1 问题描述

给定字符串s和t，判断s是否为t的子序列。子序列的定义与1143题相同。

示例： 输入：s = "abc", t = "ahbgdc" 输出：true

5.2 双指针解法

最简单的解法是使用双指针：

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 动态规划解法

也可以使用类似LCS的DP方法：

def isSubsequence(s: str, t: str) -> bool: m, n = len(s), len(t) dp = [[0]*(n+1) for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+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[m][n] == len(s)

6. 动态规划问题总结

6.1 解题思路

  1. 定义状态：明确dp数组的含义
  2. 确定状态转移方程：找出dp[i]与之前状态的关系
  3. 初始化：确定边界条件
  4. 确定遍历顺序
  5. 举例推导dp数组

6.2 常见错误

  1. 状态定义不准确
  2. 边界条件处理不当
  3. 遍历顺序错误
  4. 空间优化时状态覆盖问题

6.3 实战技巧

  1. 先画状态转移表帮助理解
  2. 打印中间结果调试
  3. 从暴力解法开始思考，再优化
  4. 注意空间优化时的状态依赖关系

7. 进阶练习建议

  1. 尝试解决LeetCode 583. 两个字符串的删除操作
  2. 挑战LeetCode 72. 编辑距离
  3. 解决LeetCode 115. 不同的子序列
  4. 尝试用多种方法解决每个问题

在实际刷题过程中，我发现动态规划问题最重要的是理解状态定义和转移方程。建议每个问题都手动推导几个例子，这样能更好地掌握DP思想。对于空间优化，一定要在完全理解二维DP后再尝试，避免过早优化导致思维混乱。