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]表示长度为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)注意这个优化版本虽然效率更高但理解起来有一定难度。建议先掌握基础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 问题特征对比特征LISLCISLCS输入数量单个数组单个数组两个数组连续性要求不连续连续连续典型解法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找出字典序最小的LISLCIS找出所有最长的连续递增序列LCS找出所有最长的重复子数组在LeetCode上寻找相关题目进行练习俄罗斯套娃信封问题LIS变种最长递增子序列的个数最长公共子序列与LCS类似但不要求连续参加周赛时注意识别题目是否与这些问题相关培养快速识别问题模式的能力。经过这样的系统训练相信你对动态规划的理解会有质的提升。记住动态规划的关键在于找到正确的状态定义和转移方程这需要大量的练习和经验积累。