企业官网建设流程全解析

1. 算法训练营Day43：动态规划经典问题精讲

今天咱们来啃动态规划里最经典的子序列问题三连击——最长递增子序列(LIS)、最长连续递增序列(LCIS)和最长重复子数组(LCS)。这几个问题不仅是面试高频考点，更是理解动态规划中"状态定义"和"状态转移"的绝佳案例。我在刷题时发现，很多同学卡在"为什么这样定义dp数组"和"如何推导状态方程"这两个关键点上，今天就用最接地气的方式带大家攻破它们。

先说说这三个问题的共性和区别：它们都在处理序列的局部特征（递增/重复），但约束条件不同。LIS允许跳跃选择元素，LCIS要求连续元素，LCS则涉及两个序列的匹配。理解这些差异对写出正确的状态转移方程至关重要。

2. 核心问题解析与DP设计原理

2.1 300.最长递增子序列(LIS)

问题本质：在无序数组中找出最长的严格递增子序列长度。例如[10,9,2,5,3,7,101,18]的LIS是[2,3,7,101]，长度为4。

DP设计要点：

1. 状态定义：dp[i]表示以nums[i]结尾的LIS长度
2. 转移方程：dp[i] = max(dp[j]) + 1 (0≤j<i且nums[j]<nums[i])
3. 初始化：每个元素至少是自己的LIS，所以dp数组全初始化为1
4. 输出：max(dp)

关键理解：为什么状态要定义为"以nums[i]结尾"？因为子序列需要比较末尾元素的大小关系，这种定义能保留必要的比较信息。

贪心+二分优化（O(nlogn)）： 维护一个tails数组，tails[k]表示长度为k+1的LIS的最小末尾元素。遍历时：

• 如果x大于tails[-1]，直接追加
• 否则二分查找第一个≥x的位置并替换

def lengthOfLIS(nums): tails = [] for num in nums: i = bisect.bisect_left(tails, num) if i == len(tails): tails.append(num) else: tails[i] = num return len(tails)

2.2 674.最长连续递增序列(LCIS)

问题特点：要求子序列必须是原数组的连续子数组。如[1,3,5,4,7]的LCIS是[1,3,5]，长度为3。

与LIS的关键区别：

• 连续性约束使得状态转移只需考虑前一个元素
• 不需要遍历之前所有元素比较

DP设计：

1. dp[i]：以nums[i]结尾的LCIS长度
2. 转移方程：
   • nums[i]>nums[i-1]时：dp[i] = dp[i-1]+1
   • 否则：dp[i] = 1
3. 空间优化：由于只依赖前一个状态，可以用单变量代替dp数组

def findLengthOfLCIS(nums): res = count = 1 for i in range(1, len(nums)): count = count + 1 if nums[i] > nums[i-1] else 1 res = max(res, count) return res

2.3 718.最长重复子数组(LCS)

问题升级：现在需要比较两个数组，找出它们的最长公共子数组长度。例如： A: [1,2,3,2,1] B: [3,2,1,4,7] 最长公共子数组是[3,2,1]，返回3。

DP设计要点：

1. 状态定义：dp[i][j]表示以A[i-1]和B[j-1]结尾的最长公共子数组长度 （使用i-1/j-1是为了方便处理边界条件）
2. 转移方程：
   • A[i-1]==B[j-1]时：dp[i][j] = dp[i-1][j-1]+1
   • 否则：dp[i][j] = 0
3. 初始化：dp[0][j]=dp[i][0]=0
4. 输出：max(max(row) for row in dp)

空间优化技巧：由于只依赖左上角状态，可以降为一维数组，注意需要从后往前遍历：

def findLength(A, B): m, n = len(A), len(B) dp = [0] * (n + 1) res = 0 for i in range(1, m + 1): for j in range(n, 0, -1): dp[j] = dp[j-1] + 1 if A[i-1] == B[j-1] else 0 res = max(res, dp[j]) return res

3. 对比分析与解题模板

3.1 三种问题的状态定义对比

3.2 动态规划解题通用模板

1. 定义状态：明确dp数组的含义
2. 状态转移：找出dp[i]与之前状态的关系
3. 初始化：设置边界条件的初始值
4. 遍历顺序：确定正确的计算顺序
5. 输出结果：从dp数组中提取最终答案

4. 常见错误与调试技巧

4.1 LIS典型错误

• 错误：直接定义dp[i]为前i个元素的LIS长度
  • 反例：[1,3,2]时，dp[2]=2，dp[3]=2，无法通过dp[2]推导dp[3]
• 修正：必须定义为"以nums[i]结尾"才能保证状态可转移

4.2 LCIS易错点

• 错误：混淆连续与不连续的区别
  • 例如在[1,3,5,4,7]中，不连续解法会得到4（1,3,5,7）
  • 正确结果应为3（1,3,5）

4.3 LCS调试技巧

• 打印dp表：二维问题建议先画出dp表格

  def print_dp(dp): for row in dp: print(' '.join(f'{num:2d}' for num in row))

• 边界检查：特别注意A[i-1]和B[j-1]的索引偏移

5. 实战练习题推荐

1. LIS变种：

   • 673.最长递增子序列的个数
   • 354.俄罗斯套娃信封问题（二维LIS）

2. LCIS扩展：

   • 487.最大连续1的个数II（带一次翻转机会）
   • 1004.最大连续1的个数III（带K次翻转）

3. LCS进阶：

   • 583.两个字符串的删除操作
   • 1143.最长公共子序列（不要求连续）

刷题建议：按LIS→LCIS→LCS的顺序练习，体会状态定义如何影响转移方程。每个问题先自己尝试写状态定义，再对比正确解法。

最后分享一个调试DP问题的小技巧：当状态转移不清晰时，可以手动计算小规模例子的dp表，观察其中的规律。比如对于LIS问题，可以用[1,4,3,4,2]这个例子一步步推导dp数组的变化过程。