DP：子序列模型 —— 从入门到精通

油墨香^_^

255人浏览 · 2026-06-06 01:33:06

油墨香^_^ · 2026-06-06 01:33:06 发布

1. 引言：什么是子序列问题

子序列 vs 子数组

在开始之前，我们必须明确两个极易混淆的概念：

子数组（Subarray）：原序列中连续的一段。例如对于数组 [1,2,3,4]，[2,3,4] 是子数组，但 [1,3,4] 不是。
子序列（Subsequence）：原序列中删除若干元素（可以不连续）后剩下的序列，保持原有的相对顺序。例如 [1,3,4] 是 [1,2,3,4] 的一个子序列。

为什么子序列问题适合 DP？
因为子序列问题通常具有最优子结构和重叠子问题的性质。当我们考虑一个序列的前缀时，其子序列的状态可以由更小的前缀推导出来，这完美契合了动态规划的思想。

2. 基础线性 DP：子序列的初步探索

2.1 最长上升子序列（LIS）

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

解法一：O(n2)O(n2) 动态规划

这是理解子序列 DP 的基石。

状态定义：
dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。

状态转移：
对于每个 i，我们检查所有在它之前的 j（0 ≤ j < i）：

如果 nums[j] < nums[i]，那么 nums[i] 可以接在以 nums[j] 结尾的上升子序列后面。
因此，dp[i] = max(dp[i], dp[j] + 1)。

初始化：
每个元素自身可以构成长度为 1 的子序列，所以 dp[i] = 1。

最终答案：
max(dp[i]) for i = 0..n-1。

python

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

复杂度：时间 O(n2)O(n2)，空间 O(n)O(n)。

解法二：贪心 + 二分 O(nlog⁡n)O(nlogn)

这是 LIS 的经典优化方法，虽然核心不是传统 DP，但思想极其重要。

核心思想：维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的末尾元素的最小可能值。

算法步骤：
遍历数组 num：

如果 num 大于 tails 中所有元素，则将其追加到 tails 末尾，表示找到了一个更长的子序列。
否则，在 tails 中找到第一个大于等于 num 的元素，并用 num 替换它（为了保持“末尾元素最小”的性质）。

为什么正确：tails 本身并不一定是 LIS，但它的长度就是 LIS 的长度。这种方法贪心地希望每个长度的子序列末尾尽可能小，以便后面能接更多的数。

python

def lengthOfLIS(nums):
    tails = []
    for num in nums:
        # 二分查找第一个大于等于 num 的位置
        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(nlog⁡n)O(nlogn)，空间 O(n)O(n)。

打印 LIS 路径

有时我们需要输出具体的子序列。在 O(n2)O(n2) DP 中，我们可以维护一个 prev 数组记录转移来源，最后回溯即可。在 O(nlog⁡n)O(nlogn) 方法中，由于贪心替换会丢失历史信息，打印路径相对复杂，通常需要额外记录每个位置作为末尾时的前驱。

2.2 最长公共子序列（LCS）

问题：给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。

基础二维 DP

状态定义：
dp[i][j] 表示 text1 的前 i 个字符（索引 0..i-1）和 text2 的前 j 个字符（索引 0..j-1）的 LCS 长度。

状态转移：

如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

初始化：
dp[0][j] = 0，dp[i][0] = 0。

python

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

复杂度：时间 O(mn)O(mn)，空间 O(mn)O(mn)。

空间优化

观察到 dp[i][j] 只依赖于当前行和上一行，可以用滚动数组将空间优化到 O(min⁡(m,n))O(min(m,n))。

特殊情况优化：转化为 LIS

当其中一个序列的元素互不相同时，LCS 可以转化为 LIS 问题，达到 O(nlog⁡n)O(nlogn) 的复杂度。

思路：将 text2 中的元素映射为它们在 text1 中的下标（如果存在）。然后求 text2 映射后序列的 LIS。这利用了 LCS 在元素不重复时的单调性。

3. 子序列 DP 的状态设计范式

在子序列问题中，如何定义状态是解题的关键。以下是几种常见范式。

3.1 以“结尾”为状态（LIS 思想）

这是处理“单序列”子序列问题最常见的方式。状态 dp[i] 通常表示“以第 i 个元素结尾的满足条件的子序列的某个性质”。

适用场景：问题要求子序列必须保持原顺序，且通常希望得到“最优”或“计数”时，我们枚举最后一个元素是什么。

变体：

最长递增子序列：dp[i] = 以 nums[i] 结尾的 LIS 长度。
最长摆动子序列：dp[i][0] 表示以 nums[i] 结尾且最后一步是上升的最长摆动序列长度；dp[i][1] 表示最后一步是下降。
最长数对链：类似 LIS。

3.2 以“位置对”为状态（LCS 思想）

处理两个序列（或一个序列与自身）的关系时使用。

适用场景：比较两个序列的前缀，或者在一个序列上做区间比较（如回文）。

典型应用：

LCS：dp[i][j]。
编辑距离（本质也是子序列的变种）。
最长回文子序列（区间 DP）。

3.3 以“长度”为状态

有时我们关心的是“长度为 L 的子序列的某个性质”，而不是以哪个元素结尾。

典型应用：

LIS 的贪心优化中的 tails 数组本质就是 dp[len] = min_last_value。
“找出所有长度为 k 的递增子序列个数”等问题。

3.4 状态压缩思想

当序列长度较小（如 n ≤ 20）时，可以用二进制掩码表示哪些元素被选中，进行枚举。这不是传统 DP 的重点，但在某些题目中是可行解。

4. 区间 DP 与子序列

4.1 最长回文子序列（LPS）

问题：给定一个字符串 s，找到其中最长的回文子序列的长度。

注意：回文子序列不要求连续，但顺序必须保持。

解法：区间 DP

状态定义：
dp[i][j] 表示子串 s[i..j] 的最长回文子序列的长度。

状态转移：

如果 s[i] == s[j]，则 dp[i][j] = dp[i+1][j-1] + 2。
否则，dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

遍历顺序：由于 dp[i][j] 依赖于 i+1 和 j-1，需要按区间长度从小到大遍历，或者从后往前遍历 i。

python

def longestPalindromeSubseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for length in range(2, n+1):  # 区间长度
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

复杂度：时间 O(n2)O(n2)，空间 O(n2)O(n2)。

转化为 LCS 的方法

将一个字符串反转后与原字符串求 LCS，得到的结果就是最长回文子序列的长度。这是因为回文序列正反读一样，所以它一定是原串和反串的公共子序列。

4.2 回文子序列计数

问题：计算字符串中回文子序列的个数（通常不要求本质不同，且长度至少为 1）。

状态定义：
dp[i][j] 表示子串 s[i..j] 中回文子序列的个数。

状态转移：

初始化：dp[i][i] = 1。
当 s[i] != s[j] 时，dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]（容斥原理）。
当 s[i] == s[j] 时，dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1（因为 s[i] 和 s[j] 可以单独配对，再加上内部的所有子序列两端加上这两个字符形成新的回文）。

4.3 删除字符使字符串成为回文串的最小操作数

等价于求“最长回文子序列”，答案为 n - LPS_length。

5. 子序列的计数问题

5.1 不同的子序列个数（允许重复字符）

问题：给定一个字符串 s，计算其所有不同的非空子序列的个数（结果取模）。

状态定义：
dp[i] 表示字符串前 i 个字符的不同子序列个数。

状态转移：

考虑第 i 个字符 c。
新增加的子序列包括：之前所有子序列后面加上 c，再加上 c 本身。
但需要去重：如果 c 之前出现过，那么上一次出现时产生的新子序列会和这次重复。
因此，dp[i] = 2 * dp[i-1] - dp[last[c] - 1]，其中 last[c] 是 c 上一次出现的位置（索引从 1 开始）。

初始化：
dp[0] = 1（代表空串），最终答案是 dp[n] - 1（去掉空串）。

5.2 本质不同的子序列个数

当要求子序列在值上本质不同（如数值数组），且值域较大时，通常使用 DP 加哈希表去重，思想与上述类似。

5.3 子序列的匹配计数

问题：给定字符串 s 和 t，计算 t 在 s 中作为子序列出现的次数。

状态定义：
dp[i][j] 表示 t 的前 j 个字符在 s 的前 i 个字符中作为子序列出现的次数。

状态转移：

dp[i][j] = dp[i-1][j]（不使用 s[i-1]）。
如果 s[i-1] == t[j-1]，则 dp[i][j] += dp[i-1][j-1]。

这是一个经典的“不同子序列”问题（LeetCode 115）。

6. 多维约束与带限制的子序列

6.1 最长 k 可重复子序列

问题：最长上升子序列中，允许每个元素最多重复 k 次。可以将每个元素复制 k 份，然后做 LIS，但更好的方法是修改二分查找的逻辑，允许相等时也接在后面。

6.2 最长摆动子序列

状态定义：
up[i] 表示以 nums[i] 结尾且最后一步是上升的最长摆动序列长度。
down[i] 表示最后一步是下降的最长摆动序列长度。

转移：

如果 nums[i] > nums[j]，则 up[i] = max(up[i], down[j] + 1)。
如果 nums[i] < nums[j]，则 down[i] = max(down[i], up[j] + 1)。

这可以 O(n2)O(n2) 实现，也可以贪心 O(n)O(n) 实现。

6.3 最长递增子序列的个数

问题：除了求 LIS 长度，还要统计有多少个不同的 LIS。

状态设计：
length[i] = 以 nums[i] 结尾的 LIS 长度。
count[i] = 以 nums[i] 结尾的 LIS 的个数。

转移：

如果 nums[j] < nums[i] 且 length[j] + 1 > length[i]，则更新 length[i] 并重置 count[i] = count[j]。
如果 length[j] + 1 == length[i]，则累加 count[i] += count[j]。

最后，统计所有 length[i] == max_len 的 count[i] 之和。

6.4 俄罗斯套娃信封问题（二维 LIS）

问题：给定信封（宽度 w，高度 h），一个信封可以放入另一个当且仅当宽度和高度都严格大于。求最多能嵌套多少层。

转化：先按宽度升序排序，如果宽度相同则按高度降序（避免宽度相同的高度被错误嵌套），然后对高度序列求 LIS 即可。

7. 高级优化技巧

7.1 树状数组 / 线段树优化 LIS

当 LIS 的值域较小（或可离散化）时，我们可以用树状数组来维护以某个值结尾的最长长度。

思路：
遍历数组，对于 nums[i]，查询所有小于 nums[i] 的值中的最大 dp 值，然后 dp[i] = query + 1，再更新树状数组在 nums[i] 位置的值。

这可以将 LIS 优化到 O(nlog⁡M)O(nlogM)，其中 M 是值域大小。

7.2 平衡树维护 DP 值

对于某些需要维护有序序列的动态 DP，可以使用平衡树（如 sortedcontainers 或手写 Treap）。

7.3 分治优化

对于 DP 转移具有单调性的问题，可以使用分治优化（如 CDQ 分治），常见于三维偏序问题（例如三维 LIS）。

8. 实战思维：如何将问题抽象为子序列模型

很多看似不相关的问题，其实都可以转化为子序列问题。

8.1 编辑距离与子序列的关系

编辑距离（Levenshtein distance）中的“插入”和“删除”操作，本质上是在寻找一个最长的公共子序列，然后通过删除和插入来对齐。最小编辑距离 = m + n - 2 * LCS 长度（当只有插入和删除时）。

8.2 子序列自动机

子序列自动机是一种预处理结构，next[i][c] 表示位置 i 之后（包括 i）字符 c 第一次出现的位置。利用它可以快速判断一个字符串是否是另一个字符串的子序列，或者进行 DP 优化。

8.3 典型例题精讲

例 1：判断子序列
给定字符串 s 和 t，判断 s 是否是 t 的子序列。双指针即可，但也可用自动机做预处理。

例 2：最短公共超序列
给定两个字符串，求包含它们作为子序列的最短字符串长度。先求 LCS，然后长度 = m + n - LCS_len。

例 3：最大整除子集
给定一组整数，找出最大的子集，其中任意两个元素存在整除关系。先排序，然后转化为 LIS（比较条件是 nums[j] % nums[i] == 0）。

9. 总结与思维导图

核心要点回顾

状态设计是关键：
- 单序列：dp[i] 以 i 结尾。
- 双序列：dp[i][j] 前缀匹配。
- 区间：dp[i][j] 子串/子数组。
转移需分情况：相等/不等、选/不选、接/不接。
优化方向：
- 空间：滚动数组。
- 时间：贪心二分、树状数组、单调性优化。
常见模型：
- LIS、LCS、LPS。
- 子序列计数、匹配计数。
- 带限制的子序列（摆动、k 重复等）。
思维拓展：很多问题（信封嵌套、编辑距离、整除子集）的本质都是 LIS 或 LCS 的变体。

思维导图（文字版）

text

子序列 DP
├── 基础模型
│   ├── LIS
│   │   ├── O(n^2) DP
│   │   ├── O(n log n) 贪心+二分
│   │   └── 打印路径
│   ├── LCS
│   │   ├── O(nm) DP
│   │   ├── 空间优化
│   │   └── 转 LIS (元素不重复)
│   └── LPS (区间 DP)
│       ├── 区间 DP 递推
│       └── 转 LCS
├── 状态设计范式
│   ├── 以结尾为状态 (LIS)
│   ├── 以位置对为状态 (LCS)
│   ├── 以长度为状态
│   └── 状态压缩
├── 计数问题
│   ├── 不同子序列个数
│   ├── 本质不同子序列
│   └── 匹配计数
├── 变体与进阶
│   ├── 最长摆动序列
│   ├── LIS 个数统计
│   ├── 俄罗斯套娃 (二维 LIS)
│   └── 带限制 LIS (k 重复)
├── 优化技巧
│   ├── 树状数组/线段树
│   ├── 平衡树
│   └── 分治优化 (CDQ)
└── 实战抽象
    ├── 编辑距离
    ├── 子序列自动机
    └── 典型例题