序列与回文 DP

动态规划 ⭐⭐ 中级 🔥 高频

💡 核心要点

序列 DP 分为两类：单串（只有一个序列，寻找其中的最优子序列）和双串（两个序列之间的匹配、比较、变换）。回文 DP 则专注于字符串的回文性质。这三类问题的状态转移都有清晰的几何直觉：双串 DP 在二维表格上移动，回文 DP 从外向内收缩。理解"最后一步"的决策，就能推导出所有转移方程。

Part 1：子序列 / 双串 DP

识别信号

遇到以下场景时，考虑子序列或双串 DP：

两个字符串/数组之间的操作：将 A 变成 B 最少需要几步？A 和 B 有多少公共部分？
匹配、对齐、变换：编辑距离、字符串交错、通配符匹配
单序列的子序列问题：最长递增子序列、最长公共子序列（退化为单串与自身）
计数问题：A 中有多少个子序列等于 B？
问题涉及"不要求连续"——注意区分子序列（可跳过）和子数组（必须连续）

通用思考框架

第一步：确定状态维度

单串问题：

例如，最长递增子序列中 dp[i] = 以 nums[i] 结尾的 LIS 长度。

双串问题：

这个二维状态的本质是：我已经"处理完"了 A[0..i-1] 和 B[0..j-1]，现在站在这个位置向后看。

为什么用"前 i 个"而非"第 i 个"？因为这样可以自然地处理空串边界：dp[0][j] 表示 A 为空时的答案，初始化更直观。

第二步：推导转移方程——看最后一对元素的决策

双串 DP 转移的核心思路：考虑 A[i] 和 B[j] 这最后一对元素，它们之间发生了什么？

情况一：A[i] == B[j]（字符匹配）

如果最后两个字符相等，我们通常可以"白拿"这个匹配，从 dp[i-1][j-1] 转移：

情况二：A[i] != B[j]（字符不匹配）

不匹配时，我们有三个选择，每个选择对应一个转移方向：

操作	转移来源	几何含义
删除 A[i]（或跳过 A[i]）	`dp[i-1][j]`	在表格中向上移动一格
删除 B[j]（或跳过 B[j]）	`dp[i][j-1]`	在表格中向左移动一格
替换（A[i] 换成 B[j]）	`dp[i-1][j-1]`	在表格中斜向左上移动

取三者的最优值（最小代价或最大收益）。

第三步：关键区分——子序列 vs 子数组

这是最容易混淆的地方，转移方程有本质区别：

子序列（不连续）：即使当前不匹配，已有的最优解仍然保留。

// 最长公共子序列——不匹配时，从相邻状态继承
if (A[i] == B[j])  dp[i][j] = dp[i-1][j-1] + 1;
else               dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
// 不匹配时 dp[i][j] 不归零，因为之前的公共子序列还在

子数组（连续）：要求连续，不匹配时当前连续段必须重新开始。

// 最长公共子数组——不匹配时，dp 归零
if (A[i] == B[j])  dp[i][j] = dp[i-1][j-1] + 1;
else               dp[i][j] = 0;  // 必须从头开始
// 答案是所有 dp[i][j] 中的最大值，而非 dp[m][n]

直觉上理解：子序列允许"跳过"不匹配的字符，所以已有的匹配成果不会被破坏；子数组要求连续，一旦断开就得重来。

第四步：初始化边界

双串 DP 的边界通常是空串情况：

dp[0][j]：A 为空时，需要插入 j 个字符才能变成 B（编辑距离）；或公共子序列长度为 0（LCS）
dp[i][0]：B 为空时，类似处理

第五步：遍历顺序与路径回溯

由于 dp[i][j] 依赖 dp[i-1][*] 和 dp[*][j-1]，外层循环 i 从 1 到 m，内层循环 j 从 1 到 n，保证计算顺序正确。

路径回溯技巧（还原具体操作序列）：

从 dp[m][n] 反向追踪：

若 A[i] == B[j]，说明此处匹配，移动到 dp[i-1][j-1]
若来自 dp[i-1][j]，说明删除了 A[i]，向上移动
若来自 dp[i][j-1]，说明删除了 B[j]，向左移动
若来自 dp[i-1][j-1]（不匹配情况），说明替换，斜向移动

典型例题：编辑距离

LeetCode 72 — 给定两个字符串 word1 和 word2，计算将 word1 转换为 word2 所需的最少操作数（插入、删除、替换各计 1 步）。

五步法分析

第一步：状态定义

第二步：转移方程

考虑 word1[i] 和 word2[j] 这最后一对字符：

若 word1[i] == word2[j]：最后一个字符天然匹配，不需要任何操作，直接继承前面的结果：
若 word1[i] != word2[j]：三种操作各对应一个转移方向：
- 插入（向 word1 插入 word2[j]）：等价于 word1 前 i 个字符已经变成了 word2 前 j-1 个，再插入一个字符：
- 删除（删除 word1[i]）：等价于 word1 前 i-1 个字符已经变成了 word2 前 j 个：
- 替换（将 word1[i] 替换为 word2[j]）：等价于 word1 前 i-1 个字符已经变成了 word2 前 j-1 个，再替换最后一个：

第三步：初始化

dp[i][0] = i：将 word1 前 i 个字符变成空串，需要删除 i 次
dp[0][j] = j：从空串变成 word2 前 j 个字符，需要插入 j 次

第四步：遍历顺序

i 从 1 到 m，j 从 1 到 n（标准左上→右下顺序）。

第五步：返回值

dp[m][n]，即将完整 word1 变成完整 word2 的最少操作数。

Java 实现

java

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        // dp[i][j]: word1[0..i-1] 变成 word2[0..j-1] 的最少操作数
        int[][] dp = new int[m + 1][n + 1];

        // 边界初始化
        for (int i = 0; i <= m; i++) dp[i][0] = i; // 删除 i 次
        for (int j = 0; j <= n; j++) dp[0][j] = j; // 插入 j 次

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // 最后字符匹配，不需要额外操作
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 三种操作取最小，各加 1 步
                    dp[i][j] = Math.min(
                        dp[i][j - 1],      // 插入：为 word1[0..i] 插入 word2[j]
                        Math.min(
                            dp[i - 1][j],      // 删除：删除 word1[i]
                            dp[i - 1][j - 1]   // 替换：word1[i] → word2[j]
                        )
                    ) + 1;
                }
            }
        }

        return dp[m][n];
    }
}

复杂度分析：

时间：，填满整个二维表格
空间：；可优化为（滚动数组，只保留当前行和上一行）

延伸题目

题目	链接	与典型题的区别	关键技巧
最长递增子序列	LC 300	单串，`dp[i]` = 以 `nums[i]` 结尾的 LIS 长度	DP；进阶：贪心 + 二分达到
最长公共子序列	LC 1143	双串标准模板，求最长公共部分	匹配时 `+1`，不匹配时取两方向最大值
不同的子序列	LC 115	计数型双串 DP，只允许删除操作	只能删不能增；`dp[i][j] = dp[i-1][j-1] + dp[i-1][j]`（匹配时可选择用或不用）
最长重复子数组	LC 718	要求连续（子数组），不匹配时 dp 归零	不匹配时 `dp[i][j] = 0`；答案是表格中的最大值而非右下角

Part 2：回文 DP

识别信号

遇到以下场景时，考虑回文 DP：

求字符串中最长回文子串或最长回文子序列
将字符串变成回文最少需要几步（插入/删除）
将字符串分割成若干回文串，求最少分割次数
判断或统计某区间 s[i..j] 是否为回文（需要预处理所有子串信息）

关键特征：问题的核心是利用回文的对称性，而且往往需要对所有子区间的回文信息进行推理。

通用思考框架

第一步：选择合适的状态定义

回文 DP 有两种常见的状态定义，针对不同问题类型：

类型 A：区间是否为回文 / 区间的最长回文长度

用于：需要预处理所有子区间回文信息，或直接求最优值的问题。

类型 B：将区间变成回文的代价

用于：回文编辑/插入类问题。

第二步：推导转移方程——两端向中间收缩

回文的本质是对称，所以转移方向是从两端向中间，而非从左到右：

当 s[i] == s[j]（两端字符相等）：

两端字符可以组成一对，问题规模缩减到内部子问题：

直觉：s[i] 和 s[j] 贡献 2 个字符，中间 s[i+1..j-1] 的最优解直接继承。

当 s[i] != s[j]（两端字符不等）：

两端不能同时保留，必须舍弃其中一个端点（或付出代价），取较优方向：

dp[i+1][j]：忽略左端 s[i]，考虑 s[i+1..j] 的结果
dp[i][j-1]：忽略右端 s[j]，考虑 s[i..j-1] 的结果

第三步：遍历顺序——长度从短到长（关键！）

这是回文 DP 最容易出错的地方。不能按 i 从小到大直接遍历，原因如下：

dp[i][j] 依赖 dp[i+1][j-1]，即依赖 i 更大、j 更小的子问题（区间更短）。

如果 i 从上到下遍历，当计算 dp[i][j] 时，dp[i+1][j-1] 还没有被计算！

正确做法：按区间长度从短到长遍历：

java

// len 是当前处理的区间长度
for (int len = 1; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        // 计算 dp[i][j]
    }
}

或者等价地，i 从大到小遍历（保证 dp[i+1][...] 先于 dp[i][...] 被计算）：

java

for (int i = n - 1; i >= 0; i--) {
    for (int j = i; j < n; j++) {
        // 计算 dp[i][j]
    }
}

为什么这样就对了？ 当 i 从 n-1 递减时，计算 dp[i][j] 时 dp[i+1][j-1] 对应更大的 i 值，已经在之前的循环轮次中计算完毕。

第四步：边界初始化

长度为 1：单个字符 dp[i][i] = 1（单字符是回文，长度为 1）
长度为 2：dp[i][i+1] = 2（如果 s[i] == s[i+1]）或 1（如果不等）

第五步：与中心扩展法的对比

方法	时间复杂度	空间复杂度	适用场景
区间 DP			需要所有子区间的回文信息（如回文分割预处理）
中心扩展			只需要最长回文子串，不需要保存子区间信息
Manacher 算法			最长回文子串的最优解，但实现复杂

选择依据： 如果后续还需要查询任意 s[i..j] 是否为回文（如回文分割 II），用区间 DP 预处理一张表；如果只需要最长回文，用中心扩展更省空间。

典型例题：最长回文子序列

LeetCode 516 — 给定字符串 s，求其最长回文子序列的长度（子序列不要求连续）。

五步法分析

第一步：状态定义

第二步：转移方程

若 s[i] == s[j]：两端字符相同，它们可以同时加入回文子序列，贡献 2 个长度：
若 s[i] != s[j]：两端不能同时加入同一回文，舍弃其中一端取较大值：

第三步：初始化

dp[i][i] = 1：单个字符本身就是长度为 1 的回文子序列

第四步：遍历顺序

i 从 n-1 到 0（从下到上），j 从 i 到 n-1（从左到右）。

第五步：返回值

dp[0][n-1]，即整个字符串的最长回文子序列长度。

Java 实现

java

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        // dp[i][j]: s[i..j] 中最长回文子序列的长度
        int[][] dp = new int[n][n];

        // 单个字符，长度为 1
        for (int i = 0; i < n; i++) dp[i][i] = 1;

        // i 从大到小，确保 dp[i+1][...] 先被计算
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    // 两端字符相同，各贡献 1，加上中间子问题
                    // 注意：当 j == i+1 时，dp[i+1][j-1] = dp[i+1][i] 未定义
                    // 由于初始化为 0，dp[i+1][i] = 0 表示空串，结果正确
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    // 两端字符不同，舍弃一端取较大值
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[0][n - 1];
    }
}

复杂度分析：

时间：，填满下三角区域
空间：；可优化为（滚动数组，每次只需上一行数据）

延伸题目

题目	链接	与典型题的区别	关键技巧
最长回文子串	LC 5	子串（连续）vs 子序列（不连续）	也可用中心扩展或 Manacher ，更省空间
回文分割 II	LC 132	两层 DP：回文判定 + 最少分割数	先用预处理 `isPalin[i][j]`，再用一维 DP 求最少切割次数

常见陷阱与调试

💡 核心要点

以下是序列 DP 和回文 DP 中最常见的几类错误，遇到 WA 时优先排查这些位置。

1. 下标偏移：1-indexed 和 0-indexed 混用

dp[i][j] 中的 i 指"前 i 个字符"（1-indexed），对应字符串下标 s.charAt(i-1)（0-indexed）。常见错误是误写成 s.charAt(i)，导致越界或结果错误。

2. 回文 DP 遍历顺序错误

直接写 for (int i = 0; i < n; i++) 会导致计算 dp[i][j] 时 dp[i+1][j-1] 尚未就绪。必须保证更短的子区间先计算，即 i 从大到小，或按长度从短到长。

3. 子序列 vs 子数组——答案位置不同

子序列问题：答案通常在 dp[m][n]（右下角）
子数组（连续）问题：答案是遍历过程中的最大值，dp[m][n] 没有意义

4. 回文 DP 边界：长度为 2 的子区间

当 j == i+1 时，dp[i+1][j-1] = dp[i+1][i]，这是一个"空区间"（j < i）。需要确认代码中对空区间的处理是否正确（通常初始化为 0，代表空子序列/空串，是合理的）。

5. 编辑距离——操作方向理解错误

dp[i][j-1] + 1 对应"插入"操作，dp[i-1][j] + 1 对应"删除"操作。具体是插入哪个字符、删除哪个字符，要结合转移定义仔细推导，不要死记方向。

6. 空间优化时注意覆盖问题

滚动数组优化时，计算 dp[i][j] 需要用到 dp[i-1][j-1]（对角线值），在覆盖之前必须用一个临时变量保存，否则该值会被提前覆盖。

序列与回文 DP ​

Part 1：子序列 / 双串 DP ​

识别信号 ​

通用思考框架 ​

第一步：确定状态维度 ​

第二步：推导转移方程——看最后一对元素的决策 ​

第三步：关键区分——子序列 vs 子数组 ​

第四步：初始化边界 ​

第五步：遍历顺序与路径回溯 ​

典型例题：编辑距离 ​

五步法分析 ​

Java 实现 ​

延伸题目 ​

Part 2：回文 DP ​

识别信号 ​

通用思考框架 ​

第一步：选择合适的状态定义 ​

第二步：推导转移方程——两端向中间收缩 ​

第三步：遍历顺序——长度从短到长（关键！） ​

第四步：边界初始化 ​

第五步：与中心扩展法的对比 ​

典型例题：最长回文子序列 ​

五步法分析 ​

Java 实现 ​

延伸题目 ​

常见陷阱与调试 ​

序列与回文 DP

Part 1：子序列 / 双串 DP

识别信号

通用思考框架

第一步：确定状态维度

第二步：推导转移方程——看最后一对元素的决策

第三步：关键区分——子序列 vs 子数组

第四步：初始化边界

第五步：遍历顺序与路径回溯

典型例题：编辑距离

五步法分析

Java 实现

延伸题目

Part 2：回文 DP

识别信号

通用思考框架

第一步：选择合适的状态定义

第二步：推导转移方程——两端向中间收缩

第三步：遍历顺序——长度从短到长（关键！）

第四步：边界初始化

第五步：与中心扩展法的对比

典型例题：最长回文子序列

五步法分析

Java 实现

延伸题目

常见陷阱与调试