1. 动态规划在子序列问题中的应用概述

动态规划（Dynamic Programming）是解决子序列问题的利器，尤其擅长处理那些需要全局最优解的序列匹配问题。在算法领域，子序列问题通常分为两大类：连续子序列和非连续子序列。连续子序列要求元素在原序列中必须相邻，而非连续子序列则允许元素之间存在间隔。

动态规划解决这类问题的核心思想在于"状态转移"——通过定义合适的状态表示，找出当前状态与之前状态之间的关系，从而避免重复计算。对于子序列问题，我们通常会定义dp[i]或dp[i][j]来表示以第i个元素结尾（或考虑前i个元素）时的某种最优解。

2. 最长递增子序列问题解析（300题）

2.1 问题定义与基本思路

最长递增子序列（Longest Increasing Subsequence, LIS）问题要求在一个无序的整数序列中找到一个子序列，使得这个子序列的元素严格递增，并且这个子序列的长度尽可能长。这里的"子序列"不要求连续，但必须保持原始顺序。

例如，对于序列[10,9,2,5,3,7,101,18]，最长的递增子序列是[2,3,7,101]，长度为4。

2.2 动态规划解法详解

2.2.1 DP数组定义

我们定义dp[i]为：以nums[i]结尾的最长递增子序列的长度。这个定义很关键，它保证了我们只需要关注以当前元素结尾的情况，而不用考虑全局。

2.2.2 状态转移方程

对于每个i，我们需要检查所有j < i的元素：

if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1)

这个方程的含义是：如果当前数字nums[i]比前面的某个数字nums[j]大，那么我们可以把nums[i]接在以nums[j]结尾的子序列后面，形成一个新的更长的子序列。

2.2.3 初始化与遍历顺序

每个dp[i]至少为1（只包含自己），所以初始化为全1数组。遍历顺序是外层循环i从1到n-1，内层循环j从0到i-1。

2.2.4 完整代码实现

class Solution { public: int lengthOfLIS(vector<int>& nums) { if(nums.size() <= 1) return nums.size(); vector<int> dp(nums.size(), 1); int result = 1; for(int i = 1; i < nums.size(); i++){ for(int j = 0; j < i; j++){ if(nums[i] > nums[j]){ dp[i] = max(dp[i], dp[j] + 1); } } result = max(result, dp[i]); } return result; } };

2.3 时间复杂度优化思路

上述解法的时间复杂度是O(n²)，对于大规模数据可能不够高效。更优的解法是使用贪心+二分查找，可以将时间复杂度降到O(nlogn)。基本思路是维护一个可能成为最长递增子序列的候选序列，对于每个新元素，用二分查找确定它的插入位置。

3. 最长连续递增序列问题（674题）

3.1 问题特点分析

与300题不同，674题要求子序列必须是连续的。这使得问题变得简单，因为每个元素只需要与前一个元素比较，而不需要与之前所有元素比较。

3.2 动态规划解法

3.2.1 DP数组定义

dp[i]表示以nums[i]结尾的最长连续递增子序列的长度。

3.2.2 状态转移方程

if nums[i] > nums[i-1]: dp[i] = dp[i-1] + 1 else: dp[i] = 1

3.2.3 代码实现

class Solution { public: int findLengthOfLCIS(vector<int>& nums) { if(nums.empty()) return 0; vector<int> dp(nums.size(), 1); int result = 1; for(int i = 1; i < nums.size(); i++){ if(nums[i] > nums[i-1]){ dp[i] = dp[i-1] + 1; result = max(result, dp[i]); } } return result; } };

3.3 空间优化技巧

由于dp[i]只依赖于dp[i-1]，我们可以用一个变量代替整个dp数组，将空间复杂度从O(n)降到O(1)。

4. 最长重复子数组问题（718题）

4.1 二维动态规划解法

4.1.1 DP数组定义

定义dp[i][j]为：以A[i-1]和B[j-1]结尾的最长公共子数组的长度。这里使用i-1和j-1是为了方便处理边界条件。

4.1.2 状态转移方程

if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = 0

4.1.3 代码实现

class Solution { public: int findLength(vector<int>& nums1, vector<int>& nums2) { int m = nums1.size(), n = nums2.size(); vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); int result = 0; for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ if(nums1[i-1] == nums2[j-1]){ dp[i][j] = dp[i-1][j-1] + 1; result = max(result, dp[i][j]); } } } return result; } };

4.2 空间优化技巧

由于dp[i][j]只依赖于左上方的dp[i-1][j-1]，我们可以将二维DP优化为一维，通过逆序遍历j来避免覆盖。

5. 最长公共子序列问题（1143题）

5.1 与重复子数组的区别

最长公共子序列（LCS）不要求连续，这是与718题的主要区别。这使得状态转移方程需要考虑更多情况。

5.2 动态规划解法

5.2.1 DP数组定义

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

5.2.2 状态转移方程

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])

5.2.3 代码实现

class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(), n = text2.size(); vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ 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]; } };

6. 不相交的线问题（1035题）

6.1 问题转化思路

1035题实际上是1143题的变种，因为绘制不相交的连线等价于找到两个序列的最长公共子序列。相同的数字可以连接，且顺序必须保持一致。

6.2 解法实现

可以直接使用1143题的解法，因为两者本质相同。

7. 最大子序和问题（53题）

7.1 动态规划解法

7.1.1 DP数组定义

dp[i]表示以nums[i]结尾的最大子序和。

7.1.2 状态转移方程

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

7.1.3 代码实现

class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; vector<int> dp(n); dp[0] = nums[0]; int result = dp[0]; for(int i = 1; i < n; i++){ dp[i] = max(nums[i], dp[i-1] + nums[i]); result = max(result, dp[i]); } return result; } };

7.2 空间优化

同样可以优化为O(1)空间，只需维护前一个状态的dp值。

8. 动态规划解题方法论总结

8.1 解题通用步骤

1. 定义DP数组的含义
2. 确定初始条件
3. 推导状态转移方程
4. 确定遍历顺序
5. 考虑空间优化

8.2 常见错误与调试技巧

• 边界条件处理不当：特别注意数组为空或只有一个元素的情况
• DP数组初始化错误：根据问题需求正确初始化
• 遍历顺序错误：确保计算当前状态时所需的前置状态已经计算
• 结果提取位置错误：有时结果不是dp[n-1]，需要在遍历过程中记录最大值

8.3 不同问题的对比分析

在实际面试和解题过程中，理解这些问题的共性和差异，能够帮助我们快速识别问题类型并选择合适的解法。动态规划虽然有一定难度，但通过大量练习和总结，可以掌握其核心思想并灵活应用。