1. 算法训练营第43天打卡动态规划经典问题精讲今天继续代码随想录算法训练营的动态规划专题我们聚焦三个经典子序列问题300题最长递增子序列、674题最长连续递增序列和718题最长重复子数组。这三个问题看似相似实则考察了动态规划的不同应用场景和状态定义技巧。作为算法面试中的高频考点子序列问题往往能区分出候选人对动态规划本质的理解程度。我在刷题和面试官经历中发现90%的候选人能写出基础解法但只有不到30%能说清楚状态转移的数学原理。本文将带你看透这三个问题的共性与差异分享我在教学过程中总结的子序列问题四步分析法。2. 问题分析与解题框架2.1 子序列问题核心特征子序列问题通常要求在一个序列中找出满足特定条件的子序列。与子数组不同子序列不要求连续但必须保持原始顺序。这类问题往往具有以下特点最优子结构问题的最优解包含子问题的最优解重叠子问题不同决策路径会重复计算相同子问题状态依赖性当前状态需要依赖之前的状态2.2 动态规划四步分析法根据代码随想录的教学体系我总结出解决子序列问题的通用框架状态定义明确dp数组的含义转移方程建立状态间的数学关系初始化确定基础case的初始值遍历顺序选择正确的计算方向重要提示在面试中建议先口头说明这四步思考过程再写代码这能展现系统化的解题思维。3. 300.最长递增子序列(LIS)3.1 问题描述给定一个整数数组nums找到其中最长严格递增子序列的长度。例如 输入nums [10,9,2,5,3,7,101,18] 输出4 解释最长递增子序列是 [2,3,7,101]3.2 标准DP解法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²) 空间复杂度O(n)关键点解析dp[i]表示以nums[i]结尾的最长递增子序列长度双层循环比较所有之前的元素初始化为1因为每个元素本身就是一个子序列3.3 贪心二分优化对于较长的序列O(n²)可能不够高效。我们可以使用更聪明的策略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(nlogn)空间O(n)实战技巧在面试中先给出标准DP解法然后主动提出可以进一步优化展示你的知识广度。4. 674. 最长连续递增序列4.1 问题特点与300题不同本题要求子序列必须是连续的。这使得问题更简单因为每个元素只需要与前一个比较。示例 输入nums [1,3,5,4,7] 输出3 解释最长连续递增序列是 [1,3,5]4.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)与300题的对比不需要dp数组只需维护当前长度只需单层循环效率更高状态转移简化为与前一个元素的比较5. 718. 最长重复子数组5.1 问题升级现在有两个数组A和B要求找到它们共有的、长度最长的子数组连续。这与前两题有本质区别输入从单序列变为双序列要求子数组必须连续需要二维DP来记录两个序列的匹配状态示例 输入 A: [1,2,3,2,1] B: [3,2,1,4,7] 输出3 解释最长重复子数组是 [3,2,1]5.2 二维DP解法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(m×n) 空间复杂度O(m×n)5.3 空间优化技巧观察到dp[i][j]只依赖左上方的值可以优化为一维数组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_len空间复杂度降为O(n)6. 对比总结与常见误区6.1 三题关键区别特征300-LIS674-LCIS718-LCS输入序列数112连续性要求非连续连续连续典型解法DP/贪心二分单次遍历二维DP时间复杂度O(n²)或O(nlogn)O(n)O(m×n)6.2 易错点警示初始化错误忘记将dp数组初始化为1或0边界处理忽略空输入或单元素情况状态混淆在718题中错误使用非连续的状态转移遍历顺序二维DP空间优化时方向错误导致值被覆盖6.3 测试用例设计建议常规case验证基本功能边界case空数组、单元素数组极端case完全递增/递减序列性能case长随机序列测试效率7. 扩展思考与变式题7.1 输出具体序列而不仅是长度以300题为例修改解法记录路径def lengthOfLIS_with_path(nums): dp [1] * len(nums) path [-1] * len(nums) # 记录前驱索引 for i in range(1, len(nums)): for j in range(i): if nums[i] nums[j] and dp[i] dp[j] 1: dp[i] dp[j] 1 path[i] j max_len max(dp) last dp.index(max_len) # 回溯路径 res [] while last ! -1: res.append(nums[last]) last path[last] return res[::-1]7.2 常见变式题最长递增子序列的个数LeetCode 673俄罗斯套娃信封问题LeetCode 354最长公共子序列LeetCode 1143不要求连续字符串的删除操作LeetCode 5838. 面试实战技巧先理清问题要求连续vs非连续单序列vs多序列明确说出状态定义和转移方程的逻辑讨论时间/空间复杂度的计算依据主动提出优化思路如二分查找或空间压缩用具体例子walk through你的解法我在面试候选人时发现能清晰解释dp[i][j]物理意义的人实际写代码时犯错率明显更低。建议在白板编码时先写出dp数组定义和示例计算过程。