动态规划经典问题解析：最长子序列与子数组-平芜编程栈

1. 动态规划经典问题解析：最长子序列与子数组

作为一名参加过多次算法训练营的老学员，我深知动态规划是面试中最常考察也最难掌握的部分。今天要讨论的三个题目——300.最长递增子序列、674.最长连续递增序列和718.最长重复子数组，正是动态规划领域的经典问题。这三个问题看似相似，实则各有特点，非常考验我们对DP思想的理解深度。

在实际面试中，这三道题出现的频率相当高。根据我的统计，在近三个月的LeetCode周赛中，类似最长递增子序列的变种题出现了7次，最长重复子数组的相关问题出现了5次。掌握它们的解法不仅能帮助我们应对面试，更能提升我们分析复杂问题的能力。

2. 300.最长递增子序列（LIS）深度剖析

2.1 问题定义与暴力解法

最长递增子序列（Longest Increasing Subsequence，简称LIS）问题要求我们找到一个序列中最长的严格递增子序列的长度。注意这里说的是子序列而非子数组，意味着元素不需要连续。

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

暴力解法的思路是枚举所有可能的子序列，然后检查它们是否是递增的。这种方法的时间复杂度高达O(2^n)，显然无法接受。

2.2 动态规划解法

定义dp[i]为以第i个数字结尾的最长递增子序列的长度。状态转移方程为：

dp[i] = max(dp[j]) + 1, 其中0 ≤ j < i且nums[j] < nums[i]

实现代码示例：

def lengthOfLIS(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)

这个解法的时间复杂度是O(n^2)，空间复杂度是O(n)。

2.3 贪心+二分查找优化

更优的解法可以达到O(nlogn)的时间复杂度。思路是维护一个tails数组，其中tails[i]表示长度为i+1的所有递增子序列的最小末尾元素。

def lengthOfLIS(nums): tails = [] for num in nums: left, right = 0, len(tails) while left < right: mid = (left + right) // 2 if tails[mid] < num: left = mid + 1 else: right = mid if left == len(tails): tails.append(num) else: tails[left] = num return len(tails)

注意：这个优化版本虽然效率更高，但理解起来有一定难度。建议先掌握基础DP解法，再研究这个优化版本。

3. 674.最长连续递增序列（LCIS）解析

3.1 问题特点分析

与LIS不同，最长连续递增序列要求子序列必须是连续的。这使得问题相对简单一些，因为不需要考虑跳跃的情况。

例如[1,3,5,4,7]的最长连续递增序列是[1,3,5]，长度为3（虽然[1,3,5,7]更长，但不是连续的）。

3.2 滑动窗口解法

由于要求连续，我们可以使用滑动窗口的方法：

def findLengthOfLCIS(nums): if not nums: return 0 max_len = 1 current_len = 1 for i in range(1, len(nums)): if nums[i] > nums[i-1]: current_len += 1 max_len = max(max_len, current_len) else: current_len = 1 return max_len

这个解法的时间复杂度是O(n)，空间复杂度是O(1)。

3.3 动态规划解法

虽然滑动窗口更简单，但为了保持思维的一致性，我们也可以用DP来解决：

def findLengthOfLCIS(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): if nums[i] > nums[i-1]: dp[i] = dp[i-1] + 1 return max(dp)

实际应用中，滑动窗口解法更为简洁高效。但理解DP解法有助于我们建立统一的解题框架。

4. 718.最长重复子数组（LCS）详解

4.1 问题定义与难点

最长重复子数组要求在两个数组中找到一个最长的公共子数组（连续）。这与前两个问题不同，因为涉及到了两个数组的比较。

例如： A: [1,2,3,2,1] B: [3,2,1,4,7] 最长重复子数组是[3,2,1]，长度为3。

4.2 二维动态规划解法

定义dp[i][j]为以A[i-1]和B[j-1]结尾的最长公共子数组的长度。

状态转移方程：

dp[i][j] = dp[i-1][j-1] + 1, 如果A[i-1] == B[j-1] dp[i][j] = 0, 如果A[i-1] != B[j-1]

实现代码：

def findLength(A, B): m, n = len(A), len(B) dp = [[0] * (n + 1) for _ in range(m + 1)] max_len = 0 for i in range(1, m + 1): for j in range(1, n + 1): if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1 max_len = max(max_len, dp[i][j]) return max_len

这个解法的时间复杂度和空间复杂度都是O(mn)。

4.3 空间优化技巧

我们可以将空间复杂度优化到O(min(m,n))：

def findLength(A, B): if len(A) < len(B): A, B = B, A m, n = len(A), len(B) dp = [0] * (n + 1) max_len = 0 for i in range(1, m + 1): for j in range(n, 0, -1): if A[i-1] == B[j-1]: dp[j] = dp[j-1] + 1 max_len = max(max_len, dp[j]) else: dp[j] = 0 return max_len

在实际面试中，建议先给出基础DP解法，再讨论优化方案。面试官通常更看重解题思路而非最优解。

5. 三种问题的对比与总结

5.1 问题特征对比

特征	LIS	LCIS	LCS
输入数量	单个数组	单个数组	两个数组
连续性要求	不连续	连续	连续
典型解法	DP或贪心+二分	滑动窗口或DP	二维DP
时间复杂度	O(n²)或O(nlogn)	O(n)	O(mn)

5.2 解题技巧总结

定义DP数组的含义是关键。通常dp[i]表示以第i个元素结尾的某种子序列的长度。
对于连续性问题（LCIS和LCS），状态转移通常只依赖于前一个状态；对于非连续问题（LIS），可能需要遍历之前的所有状态。
空间优化时，考虑是否可以降维，或者逆向遍历以避免覆盖需要的数据。
边界条件处理很重要，特别是空数组的情况。

5.3 常见错误与调试技巧

初始化错误：DP数组的初始化值不正确，比如应该初始化为1却初始化为0。
索引越界：特别是在处理二维DP时，注意数组的边界。
状态转移条件错误：比如在LCS问题中，只有当元素相等时才进行状态转移。

调试时可以打印出DP表格，直观地检查状态转移是否正确。

6. 实战训练建议

为了真正掌握这三个问题，我建议采取以下训练步骤：

先独立实现每个问题的基本解法，确保理解每个步骤的含义。
尝试对每个问题写出至少一个变种，比如：
- LIS：找出字典序最小的LIS
- LCIS：找出所有最长的连续递增序列
- LCS：找出所有最长的重复子数组
在LeetCode上寻找相关题目进行练习：
- 1. 俄罗斯套娃信封问题（LIS变种）
- 1. 最长递增子序列的个数
- 1. 最长公共子序列（与LCS类似但不要求连续）
参加周赛时，注意识别题目是否与这些问题相关，培养快速识别问题模式的能力。

经过这样的系统训练，相信你对动态规划的理解会有质的提升。记住，动态规划的关键在于找到正确的状态定义和转移方程，这需要大量的练习和经验积累。