1. 动态规划经典问题精讲：最长子序列三连击
今天咱们来啃动态规划里最经典的骨头——最长子序列问题。这三个题目看似相似，实则各有玄机，很多同学在面试和刷题时容易混淆。我结合自己刷了300+道动态规划题的经验，给大家拆解这三个问题的核心差异和解题套路。
先说说为什么这三个题目值得放在一起对比学习。它们都涉及"最长子序列"这个概念，但约束条件不同：300题是最长递增子序列（LIS），不要求连续；674题要求连续递增；718题则是两个数组的最长公共子数组（要求连续）。理解这些细微差别，对掌握动态规划的状态定义至关重要。
2. LeetCode 300. 最长递增子序列（LIS）
2.1 问题本质与暴力解法
给定一个无序整数数组nums，找到其中最长严格递增子序列的长度。子序列不要求连续，但相对顺序不能改变。例如[10,9,2,5,3,7,101,18]的最长递增子序列是[2,3,7,101]，长度为4。
最直观的暴力解法是枚举所有子序列，检查是否递增。一个长度为n的数组有2^n个子序列，时间复杂度O(2^n)，显然不可行。
2.2 动态规划解法
定义dp[i]为以nums[i]结尾的最长递增子序列长度。状态转移方程：
dp[i] = max(dp[j]) + 1, 其中0 ≤ j < i且nums[j] < nums[i]初始化时每个dp[i]至少为1（自身构成子序列）。最终结果是dp数组中的最大值。
def lengthOfLIS(nums): 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) if dp else 0时间复杂度O(n^2)，空间复杂度O(n)。
2.3 贪心+二分优化
更优的解法是用贪心思想维护一个递增序列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)时间复杂度降为O(n log n)，适合处理大规模数据。
关键点：理解tails数组的含义——维护的是"相同长度下末尾最小"的子序列，这样后续元素更容易接上。
3. LeetCode 674. 最长连续递增序列
3.1 与300题的差异
本题要求子序列必须是连续的，这实际上简化为寻找最长的递增连续子数组。例如[1,3,5,4,7]的最长连续递增序列是[1,3,5]，长度为3。
3.2 滑动窗口解法
由于要求连续，可以用滑动窗口维护当前递增区间：
def findLengthOfLCIS(nums): if not nums: return 0 max_len = curr_len = 1 for i in range(1, len(nums)): if nums[i] > nums[i-1]: curr_len += 1 max_len = max(max_len, curr_len) else: curr_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[i]只与dp[i-1]有关，状态转移更简单。
4. LeetCode 718. 最长重复子数组
4.1 二维动态规划解法
给两个整数数组A和B，返回两个数组中公共的、长度最长的子数组的长度。这里的子数组要求连续。
定义dp[i][j]为以A[i-1]和B[j-1]结尾的最长公共子数组长度（i,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)，空间复杂度O(mn)。
4.2 空间优化解法
观察到dp[i][j]只依赖dp[i-1][j-1]，可以优化空间：
def findLength(A, B): m, n = len(A), len(B) max_len = 0 dp = [0] * (n + 1) 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空间复杂度降为O(n)。
4.3 滑动窗口解法
还有一种巧妙的滑动窗口对齐方法，通过偏移量对齐两个数组：
def findLength(A, B): def maxLength(addA, addB, length): max_len = k = 0 for i in range(length): if A[addA + i] == B[addB + i]: k += 1 max_len = max(max_len, k) else: k = 0 return max_len m, n = len(A), len(B) result = 0 for i in range(m): length = min(n, m - i) result = max(result, maxLength(i, 0, length)) for j in range(n): length = min(m, n - j) result = max(result, maxLength(0, j, length)) return result时间复杂度O((m+n)*min(m,n))，空间复杂度O(1)。
5. 三题对比与常见误区
5.1 状态定义差异总结
| 题目 | 状态定义 | 连续性要求 | 转移方程特点 |
|---|---|---|---|
| 300 | dp[i]: 以nums[i]结尾的LIS长度 | 不连续 | 需要遍历之前所有元素 |
| 674 | dp[i]: 以nums[i]结尾的连续递增序列长度 | 必须连续 | 只与前一个元素有关 |
| 718 | dp[i][j]: 以A[i-1]和B[j-1]结尾的最长公共子数组 | 必须连续 | 需要两个维度，且要求元素相等 |
5.2 常见错误与调试技巧
边界条件处理：
- 空数组输入
- 单元素数组
- 所有元素相同的情况
初始化问题：
- 300题每个dp[i]至少为1
- 718题dp数组要多开一行一列
状态转移混淆：
- 674题误用300题的转移方式
- 718题忘记在不相等时重置dp值
调试建议：先用小例子手动计算dp表格，再与程序输出对比。
6. 实战应用与扩展
6.1 面试变种问题
- 输出具体的LIS而不仅是长度（300题）
- 最长递增子序列的个数（300题变种）
- 允许有一个"波动"的最长递增序列（如[1,3,2,4]）
- 三维的最长公共子数组（718题升维）
6.2 工程应用场景
- 版本差异比对（如git diff的算法基础）
- DNA序列比对（生物信息学）
- 文本相似度计算（自然语言处理）
- 股票趋势分析（金融领域）
6.3 刷题训练建议
建议刷题顺序：
- 先674（最简单）
- 再300（理解不连续的情况）
- 最后718（二维DP）
同类题目推荐：
- 最长公共子序列（不要求连续）
- 不相交的线（718题的变种）
- 不同的子序列（更难的状态转移）
我个人的刷题心得是：每天坚持做2-3道DP题，连续一个月后会有质的飞跃。初期可以先把经典题型的模板背下来，再慢慢理解内在逻辑。这三道题建议手写DP表格至少5次，直到能闭眼画出状态转移过程。
