1. 动态规划经典问题精讲最长子序列三连击今天咱们来啃动态规划里最经典的骨头——最长子序列问题。这三个题目看似相似实则各有玄机很多同学在面试和刷题时容易混淆。我结合自己刷了300道动态规划题的经验给大家拆解这三个问题的核心差异和解题套路。先说说为什么这三个题目值得放在一起对比学习。它们都涉及最长子序列这个概念但约束条件不同300题是最长递增子序列LIS不要求连续674题要求连续递增718题则是两个数组的最长公共子数组要求连续。理解这些细微差别对掌握动态规划的状态定义至关重要。2. LeetCode 300. 最长递增子序列LIS2.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]表示长度为i1的子序列的最小末尾元素。遍历时用二分查找确定当前元素的位置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 动态规划解法虽然滑动窗口更优但为了保持解法统一也可以用DPdef 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]*(n1) for _ in range(m1)] max_len 0 for i in range(1, m1): for j in range(1, n1): 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((mn)*min(m,n))空间复杂度O(1)。5. 三题对比与常见误区5.1 状态定义差异总结题目状态定义连续性要求转移方程特点300dp[i]: 以nums[i]结尾的LIS长度不连续需要遍历之前所有元素674dp[i]: 以nums[i]结尾的连续递增序列长度必须连续只与前一个元素有关718dp[i][j]: 以A[i-1]和B[j-1]结尾的最长公共子数组必须连续需要两个维度且要求元素相等5.2 常见错误与调试技巧边界条件处理空数组输入单元素数组所有元素相同的情况初始化问题300题每个dp[i]至少为1718题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次直到能闭眼画出状态转移过程。