第 16 课：动态规划专题（二）—— 子序列与子数组问题：面试最高频的 DP 题型

子序列和子数组问题是面试中出现频率最高的动态规划题型，没有之一。它们看似变化多端，但实际上都有固定的解题套路。这一课我们会彻底搞懂这两类问题的本质，掌握它们的通用模板，以后遇到任何子序列 / 子数组问题都能快速找到思路。

一、先搞清楚：子序列 vs 子数组

这是最容易混淆的两个概念，必须先分清楚：

• 子数组（Subarray）：数组中连续的一段元素
  • 例：数组[1,2,3,4]的子数组有[1,2]、[2,3,4]，但[1,3]不是子数组
• 子序列（Subsequence）：数组中不连续但保持相对顺序的一段元素
  • 例：数组[1,2,3,4]的子序列有[1,3]、[2,4]、[1,3,4]

✅ 记住：子数组一定是子序列，但子序列不一定是子数组。

二、子序列问题：动态规划的主战场

子序列问题是动态规划最擅长解决的问题，因为它天然满足重叠子问题和最优子结构。

题型 1：单个数组的子序列问题

母题：LeetCode 300. 最长递增子序列（LIS）

题目：给你一个整数数组nums，找到其中最长严格递增子序列的长度。

用四步走拆解

1. 定义 dp 数组：dp[i]表示以nums[i]结尾的最长递增子序列的长度
   • ✅ 这是单个数组子序列问题最常用的 dp 定义方式
2. 状态转移方程：对于每个i，遍历所有j < i：
   • 如果nums[j] < nums[i]，那么dp[i] = max(dp[i], dp[j] + 1)
   • 意思是：如果nums[i]可以接在nums[j]后面，那么以nums[i]结尾的最长递增子序列长度就是dp[j] + 1
3. 初始化：所有dp[i] = 1（每个元素本身就是一个长度为 1 的子序列）
4. 遍历顺序：从前往后遍历i，对于每个i，从前往后遍历j（0 <= j < i）

代码

python

运行

def lengthOfLIS(nums): """ 计算最长递增子序列的长度 核心思路：动态规划 (Dynamic Programming) """ # 边界情况处理：如果数组为空，长度为0 if not nums: return 0 n = len(nums) # 1. 定义并初始化 dp 数组 # dp[i] 的定义：以 nums[i] 这个数结尾的最长递增子序列的长度 # 初始化：每个元素本身至少可以构成一个长度为 1 的子序列 dp = [1] * n print(f"初始数组: {nums}") print(f"初始DP表: {dp} (每个位置初始长度为1)\n") # 2. 开始填表 # 外层循环：遍历每一个元素，把它当作“结尾” for i in range(n): # 内层循环：在 i 之前查找所有比 nums[i] 小的元素 nums[j] for j in range(i): # 只有当 nums[i] > nums[j] 时，nums[i] 才能接在 nums[j] 后面形成更长的递增序列 if nums[i] > nums[j]: # 状态转移方程： # 更新 dp[i]，看是保持原来的长度大，还是接在 dp[j] 后面（长度+1）更大 dp[i] = max(dp[i], dp[j] + 1) # 打印每一步 i 结束后的 dp 状态（方便理解过程） print(f"处理到下标 i={i} (值={nums[i]}) 后的DP表: {dp}") # 3. 返回结果 # 注意：最长递增子序列不一定以最后一个元素 nums[n-1] 结尾 # 所以我们要返回整个 dp 数组中的最大值 return max(dp) # --- 测试代码 --- if __name__ == "__main__": # 示例输入 nums_input = [10, 9, 2, 5, 3, 7, 101, 18] # 调用函数 result = lengthOfLIS(nums_input) print("-" * 30) print(f"最终结果: 最长递增子序列的长度为 {result}") # 预期输出逻辑解释： # 其中一个最长递增子序列是 [2, 3, 7, 18] 或者 [2, 3, 7, 101]，长度为 4。

优化：二分法（时间复杂度 O (nlogn)）

上面的解法时间复杂度是 O (n²)，对于大数据量会超时。有一个更优的二分法解法，时间复杂度 O (nlogn)，面试中如果能写出来会非常加分。

衍生题 1：LeetCode 674. 最长连续递增序列

题目：给定一个未经排序的整数数组，找到最长且连续递增的子序列的长度。

• 这其实是一个子数组问题，解法比 LIS 简单得多，只需要一次遍历即可。

衍生题 2：LeetCode 354. 俄罗斯套娃信封问题

题目：给你一个二维整数数组envelopes，其中envelopes[i] = [w_i, h_i]表示第 i 个信封的宽度和高度。如果另一个信封的宽度和高度都比这个信封大，那么这个信封就可以放进另一个信封里。请问最多能有多少个信封组成一组 "俄罗斯套娃" 信封？

• 解法：先按宽度升序排序，宽度相同则按高度降序排序，然后问题转化为求高度数组的最长递增子序列长度。

题型 2：两个数组的子序列问题

母题：LeetCode 1143. 最长公共子序列（LCS）

题目：给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。

用四步走拆解

1. 定义 dp 数组：dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列长度
   • ✅ 这是两个数组 / 字符串子序列问题最常用的 dp 定义方式
2. 状态转移方程：
   • 如果text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1（两个字符相同，公共子序列长度加 1）
   • 如果text1[i-1] != text2[j-1]：dp[i][j] = max(dp[i-1][j], dp[i][j-1]（取去掉 text1 第 i 个字符或去掉 text2 第 j 个字符的最大值）
3. 初始化：dp[0][j] = 0，dp[i][0] = 0（空字符串的公共子序列长度为 0）
4. 遍历顺序：从前往后遍历i和j

代码

python

运行

def longestCommonSubsequence(text1, text2): """ 计算两个字符串的最长公共子序列长度 """ m, n = len(text1), len(text2) # 1. 初始化 DP 表格 # 创建一个 (m+1) x (n+1) 的二维数组，初始值为 0 # 多出来的一行一列（第0行和第0列）代表空字符串的情况，方便处理边界 dp = [[0] * (n + 1) for _ in range(m + 1)] # 2. 填表过程 # i 代表 text1 的前 i 个字符，j 代表 text2 的前 j 个字符 for i in range(1, m + 1): for j in range(1, n + 1): # 注意：dp[i][j] 对应的是 text1[i-1] 和 text2[j-1]（因为 dp 多了一行一列） if text1[i - 1] == text2[j - 1]: # 情况 A：字符相同 # 当前长度 = 左上角的值 + 1 dp[i][j] = dp[i - 1][j - 1] + 1 else: # 情况 B：字符不同 # 当前长度 = max(上方的值, 左方的值) # 意味着：要么忽略 text1 的这个字符，要么忽略 text2 的这个字符，取最大值 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # 返回右下角的值，即两个完整字符串的最长公共子序列长度 return dp[m][n] # --- 示例测试与运行 --- if __name__ == "__main__": # 示例 1 s1 = "abcde" s2 = "ace" # 预期输出：3 ("ace" 是公共子序列) result1 = longestCommonSubsequence(s1, s2) print(f"字符串 1: '{s1}'") print(f"字符串 2: '{s2}'") print(f"最长公共子序列长度: {result1}") print("-" * 30) # 示例 2 s3 = "abc" s4 = "def" # 预期输出：0 (没有公共子序列) result2 = longestCommonSubsequence(s3, s4) print(f"字符串 1: '{s3}'") print(f"字符串 2: '{s4}'") print(f"最长公共子序列长度: {result2}")

✅ 这是所有两个字符串子序列问题的通用模板，几乎所有这类问题都是在这个模板上修改的。

衍生题 1：LeetCode 72. 编辑距离

题目：给你两个单词word1和word2，请你计算出将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

• 解法：dp 定义和 LCS 完全一样，只是状态转移方程不同。

衍生题 2：LeetCode 115. 不同的子序列

题目：给定一个字符串s和一个字符串t，计算在s的子序列中t出现的个数。

• 解法：同样是二维 dp 数组，状态转移方程略有不同。

三、子数组问题：动态规划 vs 滑动窗口

子数组问题因为元素是连续的，所以有两种常用解法：

1. 动态规划：适用于求最值、求和等问题
2. 滑动窗口：适用于求满足条件的最长 / 最短子数组长度、子数组个数等问题

题型 1：动态规划解法

母题：LeetCode 53. 最大子数组和

题目：给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

用四步走拆解

1. 定义 dp 数组：dp[i]表示以nums[i]结尾的最大子数组和
2. 状态转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])
   • 意思是：以nums[i]结尾的最大子数组和，要么是nums[i]本身，要么是dp[i-1] + nums[i]（接在前面的子数组后面）
3. 初始化：dp[0] = nums[0]
4. 遍历顺序：从前往后遍历

代码

python

运行

def maxSubArray(nums): """ 使用动态规划解决最大子数组和问题 """ n = len(nums) if n == 0: return 0 # 1. 定义 dp 数组 # dp[i] 表示：以 nums[i] 这个数结尾的连续子数组的最大和 dp = [0] * n # 2. 初始化 # 第一个元素结尾的子数组只能是它自己 dp[0] = nums[0] print(f"数组: {nums}") print(f"dp[0] = {nums[0]} (初始化)") # 3. 状态转移（从第二个元素开始遍历） for i in range(1, n): # 核心逻辑： # 如果 dp[i-1] 是正数，说明前面的累积对我们有帮助，那就加上它。 # 如果 dp[i-1] 是负数，说明前面的累积是累赘，不如直接从 nums[i] 重新开始。 dp[i] = max(nums[i], dp[i - 1] + nums[i]) print(f"i={i} (值={nums[i]}): max({nums[i]}, {dp[i-1]} + {nums[i]}) = {dp[i]}") # 4. 返回结果 # 注意：最大子数组和不一定以最后一个元素结尾，所以要在整个 dp 数组中找最大值 result = max(dp) print(f"DP表状态: {dp}") print(f"最大子数组和: {result}") return result # --- 测试运行 --- if __name__ == "__main__": # 示例输入：经典的负数陷阱案例 # 预期结果：6 (对应的子数组是 [4, -1, 2, 1]) input_data = [-2, 1, -3, 4, -1, 2, 1, -5, 4] print("--- 开始计算 ---") maxSubArray(input_data)

空间优化

因为dp[i]只依赖于dp[i-1]，所以可以用一个变量代替整个 dp 数组，空间复杂度优化到 O (1)。

衍生题：LeetCode 152. 乘积最大子数组

题目：给你一个整数数组nums，请你找出数组中乘积最大的非空连续子数组，并返回该子数组所对应的乘积。

• 解法：和最大子数组和类似，但需要同时维护最大乘积和最小乘积，因为负数乘以负数会变成正数。

题型 2：滑动窗口解法

滑动窗口解法的时间复杂度是 O (n)，比动态规划更高效，适用于所有满足单调性的子数组问题。

适用场景

• 求满足条件的最长子数组长度
• 求满足条件的最短子数组长度
• 求满足条件的子数组个数

经典例题：LeetCode 209. 长度最小的子数组

题目：给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其和>= target的长度最小的连续子数组，并返回其长度。如果不存在满足条件的子数组，返回 0。

代码

python

运行

def minSubArrayLen(target, nums): """ 使用滑动窗口法寻找和 >= target 的最短子数组长度 """ n = len(nums) if n == 0: return 0 left = 0 # 滑动窗口左边界 current_sum = 0 # 当前窗口内的元素和 min_len = float('inf') # 记录最小长度，初始化为无穷大 print(f"目标值 (target): {target}") print(f"数组 (nums): {nums}") print("-" * 30) # 1. 右指针向右移动，扩大窗口 for right in range(n): current_sum += nums[right] # 打印当前窗口状态 # print(f"窗口扩大: 右边界={right}, 当前和={current_sum}") # 2. 当窗口内的和满足条件 (>= target) 时，尝试收缩左边界 while current_sum >= target: # 更新最小长度：当前窗口大小为 (right - left + 1) min_len = min(min_len, right - left + 1) # 打印找到的符合条件窗口 print(f"找到解: 区间 [{left}, {right}], 和={current_sum}, 长度={right-left+1}") # 准备移动左边界：先减去左边界的值 current_sum -= nums[left] # 左边界右移 left += 1 # 3. 返回结果 # 如果 min_len 没变过（仍为无穷大），说明没有找到，返回 0 return min_len if min_len != float('inf') else 0 # --- 测试运行 --- if __name__ == "__main__": # 示例 1 t1 = 7 n1 = [2, 3, 1, 2, 4, 3] print("=== 测试用例 1 ===") res1 = minSubArrayLen(t1, n1) print(f"最终结果: {res1}") print("\n") # 示例 2 t2 = 11 n2 = [1, 1, 1, 1, 1, 1, 1, 1] print("=== 测试用例 2 ===") res2 = minSubArrayLen(t2, n2) print(f"最终结果: {res2}")

四、解题技巧总结

子序列问题解题模板

1. 单个数组：
   • dp 定义：dp[i]表示以nums[i]结尾的 xxx
   • 状态转移：遍历j < i，根据nums[j]和nums[i]的关系更新dp[i]
2. 两个数组 / 字符串：
   • dp 定义：dp[i][j]表示arr1前i个元素和arr2前j个元素的 xxx
   • 状态转移：根据arr1[i-1]和arr2[j-1]的关系更新dp[i][j]

子数组问题解题模板

1. 求最值、求和：用动态规划，dp[i]表示以nums[i]结尾的 xxx
2. 求满足条件的长度、个数：用滑动窗口，时间复杂度 O (n)