企业官网建设流程全解析

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]表示长度为i+1的所有递增子序列的最小末尾值。

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_len

4. 最长重复子数组

4.1 二维动态规划

718题要求两个数组的最长公共子数组（连续）。这与前两题的主要区别在于：

1. 涉及两个数组
2. 要求子数组连续

定义dp[i][j]为以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)，空间复杂度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_len

5. 对比总结与常见错误

5.1 三题对比

5.2 常见错误点

1. 混淆子序列和子数组：

   • 子序列可以不连续
   • 子数组必须连续

2. 状态转移方程错误：

   • 300题容易漏掉内层循环比较所有前面元素
   • 718题容易写成不连续的情况

3. 边界条件处理：

   • 空数组情况
   • 单元素情况
   • 完全逆序数组情况

5.3 测试用例设计

建议测试时包含以下情况：

• 空数组
• 单元素数组
• 完全递增数组
• 完全递减数组
• 随机波动数组
• 有多个相同长度的解的情况

6. 实际应用场景

这三个算法在实际中有广泛应用：

1. 最长递增子序列：

   • 基因序列分析
   • 股票趋势预测
   • 数据压缩

2. 最长连续递增序列：

   • 传感器数据分析
   • 用户行为模式识别
   • 日志异常检测

3. 最长重复子数组：

   • 文档相似度比较
   • 抄袭检测
   • 生物信息学中的序列比对

7. 扩展思考

1. 如何修改算法返回具体的子序列而不仅仅是长度？
2. 如果有多个相同长度的解，如何返回所有解？
3. 如果数据量非常大（比如n=10^6），如何优化空间使用？
4. 如果允许最多k次不连续，如何修改算法？

在解决这些问题时，我发现动态规划最难的部分不是写出代码，而是准确理解问题并设计出正确的状态表示。建议初学者多画状态转移图，从简单例子入手，逐步验证自己的思路。