1. 动态规划经典问题实战解析今天继续我们的算法训练营打卡系列来啃下动态规划中三个经典子序列问题300.最长递增子序列、674.最长连续递增序列和718.最长重复子数组。这三个问题看似相似实则各有特点是面试中区分候选人动态规划掌握程度的试金石。动态规划问题的核心在于状态定义和转移方程这三个问题恰好展示了不同场景下的状态设计思路。2. 最长递增子序列LIS问题2.1 问题理解与暴力解法最长递增子序列Longest Increasing Subsequence要求找到一个序列中最长的严格递增子序列的长度。注意子序列不要求连续。以示例 [10,9,2,5,3,7,101,18] 为例暴力解法时间复杂度为O(2^n)显然不可行我们需要找到重叠子问题这正是动态规划的用武之地2.2 动态规划解法定义dp[i]为以nums[i]结尾的最长递增子序列长度def lengthOfLIS(nums): dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] nums[j]: dp[i] max(dp[i], dp[j] 1) return max(dp)时间复杂度O(n^2)空间复杂度O(n)2.3 优化解法贪心二分查找更优的解法可以达到O(nlogn)def lengthOfLIS(nums): tails [] for num in nums: idx bisect.bisect_left(tails, num) if idx len(tails): tails.append(num) else: tails[idx] num return len(tails)这个解法维护一个tails数组其中tails[i]表示长度为i1的所有递增子序列的最小末尾值。3. 最长连续递增序列3.1 问题特点分析674题要求的是连续递增子序列这与300题的关键区别在于连续二字。这使得问题简化了不少。示例 [1,3,5,4,7]最长连续递增序列是[1,3,5]长度为3注意虽然[1,3,5,7]更长但不是连续的3.2 动态规划解法定义dp[i]为以nums[i]结尾的最长连续递增子序列长度def findLengthOfLCIS(nums): 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)由于连续性的限制内层循环被省略时间复杂度降为O(n)3.3 滑动窗口优化实际上这个问题可以不用DP用滑动窗口更直观def findLengthOfLCIS(nums): 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_len4. 最长重复子数组4.1 二维动态规划718题要求两个数组的最长公共子数组连续。这与前两题的主要区别在于涉及两个数组要求子数组连续定义dp[i][j]为以A[i-1]和B[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 空间优化可以优化到O(n)空间def findLength(A, B): 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_len5. 对比总结与常见错误5.1 三题对比题目是否连续涉及数组数典型解法时间复杂度300否1DP/贪心O(n^2)/O(nlogn)674是1DP/滑动窗口O(n)718是2二维DPO(mn)5.2 常见错误点混淆子序列和子数组子序列可以不连续子数组必须连续状态转移方程错误300题容易漏掉内层循环比较所有前面元素718题容易写成不连续的情况边界条件处理空数组情况单元素情况完全逆序数组情况5.3 测试用例设计建议测试时包含以下情况空数组单元素数组完全递增数组完全递减数组随机波动数组有多个相同长度的解的情况6. 实际应用场景这三个算法在实际中有广泛应用最长递增子序列基因序列分析股票趋势预测数据压缩最长连续递增序列传感器数据分析用户行为模式识别日志异常检测最长重复子数组文档相似度比较抄袭检测生物信息学中的序列比对7. 扩展思考如何修改算法返回具体的子序列而不仅仅是长度如果有多个相同长度的解如何返回所有解如果数据量非常大比如n10^6如何优化空间使用如果允许最多k次不连续如何修改算法在解决这些问题时我发现动态规划最难的部分不是写出代码而是准确理解问题并设计出正确的状态表示。建议初学者多画状态转移图从简单例子入手逐步验证自己的思路。