动态规划 · 序列 DP
从 LC 300 出发，看单序列 LIS、双序列 LCS 与编辑距离的状态定义和转移。
1. 核心原理
序列 DP 是动态规划里最常见的一族，处理"在序列上选 / 不选 / 配对 / 删改"等子结构问题：最长递增子序列（LIS）、最长公共子序列（LCS）、最大子段和、编辑距离、不同子序列数等都属于这一类。它和"决策序列长成树"的回溯不同——序列 DP 不要求枚举所有可能性，只要把"以某个位置为终点 / 前缀考虑到某个位置"的最优值记录下来，转移时复用即可。
朴素思路是枚举所有子序列。n 个元素的子序列共 2^n 个，再判断递增 / 配对，复杂度 O(2^n × n)，n = 30 已不可行。序列 DP 的核心 invariant 是子序列的最优结构可以挂在某个"端点"上：以 nums[i] 结尾的最长递增子序列长度，等于"前面所有可接的 j 中 f[j] 的最大值再加一"。把所有可能的端点用 O(n²) 枚举完，就得到全局答案。
状态定义的两种约定
序列 DP 的状态定义有两类常用约定：
- 约定 A：以
i结尾。f[i]表示"以nums[i]结尾的最优值"，强制nums[i]被选进序列。用在 LIS、最大子段和等"子数组 / 单序列必含末位元素"的场景。最终答案常常是max(f)，因为最优解不一定恰好以最后一个元素结尾。 - 约定 B：前
i个。f[i]表示"考虑nums[0..i-1]的最优值"，是否使用nums[i - 1]不强制。用在 LCS、编辑距离、打家劫舍等"双序列 / 不强制末位"的场景。最终答案就是f[n]，边界f[0]是"空序列"的解。
子数组类（连续段）多用约定 A；子序列类（不必连续）和双序列类多用约定 B。两者在转移与边界上各有取舍。
转移：枚举端点 / 配对
约定 A 下，f[i] 通常由"前面某个 f[j]（j < i）"加上一步贡献得到。LIS 的转移是 f[i] = 1 + max(f[j])，其中 j < i 且 nums[j] < nums[i]。这是一种"枚举上一个端点"的形式，内层循环扫一遍 [0, i)，整体 O(n²)。
约定 B 下，双序列 DP 的转移看两个端点 nums1[i - 1] 和 nums2[j - 1] 的关系：相等就走对角线（同时使用），不等就在"放弃 nums1[i - 1]" / "放弃 nums2[j - 1]"中取最优。状态空间 O(mn)，整体 O(mn)。
LIS 的二分优化
LIS 的 O(n²) 转移每个 i 都要扫前缀里的"最大 f[j]"，这个最大值可以用辅助数据结构 tails[] 维护——tails[k] 表示"所有长度为 k + 1 的递增子序列里、最后一个元素的最小值"。对每个新进来的 x，在 tails[] 里二分找位置：能扩展就追加，不能就替换。复杂度降到 O(n log n)，是 LIS 的"经典加速"，常被称为 patience sort。本章模板用 O(n²) 版本，二分优化的具体写法留到 §3 母题里。
三类速查：单序列 / 双序列 / 子数组 vs 子序列
序列 DP 再抽象一层有三类。单序列：状态只跟"当前考虑到第几个元素"有关。
| 题 | 状态定义 | 典型转移 |
|---|---|---|
| LC 300 LIS | f[i] = 以 nums[i] 结尾的 LIS 长度 | f[i] = max(f[j]) + 1，j<i 且满足条件 |
| LC 53 最大子段和 | f[i] = 以 nums[i] 结尾的最大子段和 | f[i] = max(f[i-1] + nums[i], nums[i]) |
| LC 198 打家劫舍 | f[i] = 前 i 个房屋能偷的最大金额 | f[i] = max(f[i-1], f[i-2] + nums[i]) |
双序列：两个指针 + 二维状态。
| 题 | 状态定义 | 转移核心 |
|---|---|---|
| LC 1143 LCS | f[i][j] = s[0..i] 和 t[0..j] 的 LCS 长度 | 字符相等就 +1，不等取 max |
| LC 72 编辑距离 | f[i][j] = s[0..i] 改成 t[0..j] 的最少操作 | 三选一：插入 / 删除 / 替换 |
| LC 583 删除操作 | f[i][j] = 让 s[0..i] 和 t[0..j] 相同的最少删除 | 删 s[i] 或 t[j] 或 s[i]==t[j] 跳过 |
子数组（连续） vs 子序列（不必连续） 是常见踩坑点：子数组必须连续（LC 53、LC 718），状态通常用约定 A "以 i 结尾"——因为子数组要连续；子序列可以跳着选（LC 300、LC 1143），两种约定都能写，但 LIS 这种"严格递增"约束下"以 i 结尾"更自然，LCS 这种"不要求末位必选"则"前 i 个"更顺。口诀：子数组用 A，子序列 / 双序列 用 B，80% 情况成立。
2. 通用模板
序列 DP 的最小骨架按"单 / 双序列"分两类。单序列以"枚举端点 j < i"为主，复杂度 O(n²)；双序列以"两层下标 i, j"为主，复杂度 O(mn)。下面给两类的最小可运行模板，覆盖 LIS / LCS / 编辑距离三种代表题的状态机。
def lis_n2(nums):
"""单序列 DP（约定 A）：以 i 结尾的最长递增子序列"""
n = len(nums)
if n == 0:
return 0
f = [1] * n # 每个位置至少自成长度 1
for i in range(1, n):
for j in range(i): # 枚举上一个端点
if nums[j] < nums[i]: # 严格递增条件
f[i] = max(f[i], f[j] + 1)
return max(f) # LIS 不一定以末位结尾
def lcs(s, t):
"""双序列 DP（约定 B）：最长公共子序列长度"""
m, n = len(s), len(t)
f = [[0] * (n + 1) for _ in range(m + 1)] # 多开一行一列存边界
for i in range(1, m + 1):
for j in range(1, n + 1):
if s[i - 1] == t[j - 1]: # 字符相等：走对角线 +1
f[i][j] = f[i - 1][j - 1] + 1
else: # 不等：放弃 s[i-1] 或 t[j-1]
f[i][j] = max(f[i - 1][j], f[i][j - 1])
return f[m][n]// 单序列 DP（约定 A）：LIS 的 O(n²) 版本
static int lisN2(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] f = new int[n];
Arrays.fill(f, 1); // 每个位置自成长度 1
int ans = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) { // 枚举上一个端点
if (nums[j] < nums[i]) { // 严格递增条件
f[i] = Math.max(f[i], f[j] + 1);
}
}
ans = Math.max(ans, f[i]);
}
return ans;
}
// 双序列 DP（约定 B）：最长公共子序列
static int lcs(String s, String t) {
int m = s.length(), n = t.length();
int[][] f = new int[m + 1][n + 1]; // 多开一行一列存边界
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
f[i][j] = f[i - 1][j - 1] + 1; // 对角线 +1
} else {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
}
}
}
return f[m][n];
}// 单序列 DP（约定 A）：LIS 的 O(n²) 版本
int lisN2(const vector<int>& nums) {
int n = (int)nums.size();
if (n == 0) return 0;
vector<int> f(n, 1); // 每个位置自成长度 1
int ans = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) { // 枚举上一个端点
if (nums[j] < nums[i]) { // 严格递增条件
f[i] = max(f[i], f[j] + 1);
}
}
ans = max(ans, f[i]);
}
return ans;
}
// 双序列 DP（约定 B）：最长公共子序列
int lcs(const string& s, const string& t) {
int m = (int)s.size(), n = (int)t.size();
vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s[i - 1] == t[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1; // 对角线 +1
} else {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
}
return f[m][n];
}四个要注意的点：
- 边界值：单序列约定 A 的
f全初始化为 1（每个位置自成长度 1 的子序列）。双序列约定 B 的f[0][*] = f[*][0] = 0（空串的 LCS 长度为 0）。编辑距离的边界则不同——f[i][0] = i, f[0][j] = j。边界写错整张表都跟着错。 - 下标偏移：双序列 DP 里
f[i][j]表示"前i个字符 / 前j个字符"，所以对应原串位置是s[i - 1]和t[j - 1]。写成s[i]是常见 off-by-one 错。 - 最终答案位置：约定 A 通常
max(f)；约定 B 通常f[m][n]。LIS 是约定 A、LCS 是约定 B，记错就 WA。 - 空间优化：双序列 DP 的
f[i][j]只依赖上一行和当前行的左侧值，可滚动到O(min(m, n))。但代码可读性下降，工程上先写二维再压。
3. 母题精讲
LeetCode 300. 最长递增子序列
链接：LeetCode 300
题意：给一个整数数组 nums，求最长严格递增子序列的长度。子序列不要求连续，只要元素相对次序不变即可。
数据范围：
1 ≤ nums.length ≤ 2500-10⁴ ≤ nums[i] ≤ 10⁴
示例：
输入：nums = [10, 9, 2, 5, 3, 7, 101, 18]
输出：4
解释：最长递增子序列是 [2, 3, 7, 101]，长度 4。注意 [2, 5, 7, 18] 也是合法答案之一，长度同样 4。进阶：能不能在 O(n log n) 内做？
暴力思路：枚举所有子序列
最朴素的解法是枚举所有 2ⁿ 个子序列，逐个检查是不是严格递增。n = 2500 时这个量级是天文数字，连样例都跑不出来。
进一步剪枝：用回溯枚举所有递增子序列，每一步要么"跳过当前元素"、要么"接到当前递增前缀后面"。这相当于在一棵深度 n 的二叉决策树上搜索，复杂度仍是 O(2ⁿ)。题目给到 n = 2500，朴素枚举无解。
O(n²) DP：以 i 结尾
转换视角：与其枚举"全局子序列"，不如枚举"以哪个位置结尾"。
定义 f[i] = "以 nums[i] 结尾的最长严格递增子序列的长度"。这个定义有个关键约束——nums[i] 必须被选进序列。
转移：要让 nums[i] 接在某个更短的递增子序列后面，只能接在某个 f[j]（j < i 且 nums[j] < nums[i]）后面。所以：
f[i] = 1 + max(f[j] for j < i if nums[j] < nums[i])
如果前面没有任何 j 满足 nums[j] < nums[i]，那就 f[i] = 1（只有它自己）。
边界：f[0] = 1（数组里第一个元素自成一个长度为 1 的子序列）。
最终答案是 max(f[i] for i in range(n))——因为题目问"最长"，而 LIS 不一定以最后一个元素结尾。
下面走一遍 nums = [10, 9, 2, 5, 3, 7, 101, 18] 的填表：
i 0 1 2 3 4 5 6 7
nums[i] 10 9 2 5 3 7 101 18
f[i] 1 1 1 2 2 3 4 4f[3] = 2：因为 nums[3] = 5 > nums[2] = 2，能接在 f[2] = 1 后面，得 1 + 1 = 2。
f[5] = 3：从 f[2]（值 1，2 < 7）、f[3]（值 2，5 < 7）、f[4]（值 2，3 < 7）三个里取最大，2 + 1 = 3。
f[6] = 4：f[5] = 3 且 nums[5] = 7 < 101，所以 3 + 1 = 4。
最大值是 f[6] = f[7] = 4，答案 4。
下面用 ArrayViz 走一遍前几步的填表：
LIS 填表过程（前 6 步）
f[i] = 1 + max(f[j])，j<i 且 nums[j]<nums[i]
复杂度 O(n²) 时间、O(n) 空间。n = 2500 时大概 6 × 10⁶ 次基本操作，C++ / Java / Go 跑得轻松，Python 也基本能压在 1s 内。
class Solution:
def lengthOfLIS_n2(self, nums: list[int]) -> int:
n = len(nums)
f = [1] * n # 每个位置至少自成长度 1
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]: # 严格递增
f[i] = max(f[i], f[j] + 1)
return max(f)注意几个细节：
f = [1] * n把所有边界都设好——任何位置至少能自成一个长度 1 的子序列。nums[j] < nums[i]是严格小于。如果题目改成"非严格递增"（允许相等），改成<=即可，但 LC 300 是严格的。- 最后返回
max(f)而不是f[-1]，因为 LIS 不一定以最后一个元素结尾。
O(n log n) 优化：二分 + tails 数组
n = 2500 还能扛，但如果 n 涨到 10⁵，O(n²) = 10¹⁰ 就跑不动了。换一个思路。
定义 tails[k] = "所有长度为 k + 1 的递增子序列里，最后一个元素的最小值"。这个数组有两个性质：
- 严格递增：
tails[0] < tails[1] < tails[2] < ...。证明：长度为k + 1的递增子序列尾部x一定来自某个长度为k的递增子序列尾部y，且y < x，所以最小化tails[k + 1]也得> tails[k]。 tails的长度就是当前 LIS 的长度。
扫一遍 nums，对每个 x = nums[i]：
- 用二分在
tails里找第一个≥ x的位置pos（即左边界二分）。 - 如果
pos == len(tails)：说明x比所有 tail 都大，可以"开新长度"——tails.append(x)。 - 否则用
x替换tails[pos]——更小的 tail 让后续更容易接上新元素。
走一遍 nums = [10, 9, 2, 5, 3, 7, 101, 18]：
读 10: tails = [] → append → tails = [10]
读 9: tails = [10] → 替换 pos=0 → tails = [9]
读 2: tails = [9] → 替换 pos=0 → tails = [2]
读 5: tails = [2] → append → tails = [2, 5]
读 3: tails = [2, 5] → 替换 pos=1 → tails = [2, 3]
读 7: tails = [2, 3] → append → tails = [2, 3, 7]
读 101: tails = [2, 3, 7] → append → tails = [2, 3, 7, 101]
读 18: tails = [2, 3, 7, 101] → 替换 pos=3 → tails = [2, 3, 7, 18]最终 len(tails) = 4，答案 4。注意 tails 数组不是 LIS 本身——它只是个辅助结构，长度等于答案。比如最后一步 tails = [2, 3, 7, 18]，但 18 在原数组里在 101 之后，真实 LIS 是 [2, 3, 7, 101] 或 [2, 5, 7, 101]。
为什么"替换"是对的？想象长度 2 的递增子序列里，尾部分别是 5 和 3——两个都有效，但 3 更小，未来更容易被某个新元素接上（接的条件是 > tail）。所以保留最小的那个永远不亏。
from bisect import bisect_left
class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
tails = []
for x in nums:
pos = bisect_left(tails, x) # 第一个 ≥ x 的下标
if pos == len(tails):
tails.append(x) # 开新长度
else:
tails[pos] = x # 替换为更小的尾部
return len(tails)复杂度 O(n log n)——每个元素一次 O(log n) 二分。空间 O(n)（tails 最长不超过 n）。
一个常见疑问：严格 vs 非严格对应 bisect_left 还是 bisect_right？
- 严格递增（
<）→bisect_left（找第一个≥ x的位置，把它替换成x）。 - 非严格递增（
≤，允许相等）→bisect_right（找第一个> x的位置）。
LC 300 是严格的，用 bisect_left。这个区别很微妙，记错就 WA。
小结：朴素枚举 vs O(n²) DP vs O(n log n) 二分
| 思路 | 时间 | 空间 | 写法 |
|---|---|---|---|
| 枚举所有子序列 | O(2ⁿ) | O(n) 递归栈 | n ≤ 20 才能跑 |
O(n²) DP（以 i 结尾） | O(n²) | O(n) | 容易写，能输出方案 |
O(n log n) 二分 + tails | O(n log n) | O(n) | 写起来要小心 bisect_left/right |
工程上，n ≤ 2500 用 O(n²) 已经足够；n 大于 10⁴ 时上 O(n log n)。两份代码都要会写，面试时面试官常追问"能不能更快"。
4. 例题（三道）
按"单序列 → 双序列匹配 → 双序列三选一"递进。
4.1 LC 300 最长递增子序列
回到本章开头那道题。上面已经讲完两种解法。下面给三语言版本。
from bisect import bisect_left
class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
# O(n log n) 版本：tails 数组 + 二分
tails = []
for x in nums:
pos = bisect_left(tails, x) # 严格递增用 bisect_left
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)
def lengthOfLIS_n2(self, nums: list[int]) -> int:
# O(n²) DP 版本：以 i 结尾
n = len(nums)
f = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
f[i] = max(f[i], f[j] + 1)
return max(f)class Solution {
public int lengthOfLIS(int[] nums) {
// O(n log n) 版本
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int lo = 0, hi = size;
while (lo < hi) { // 手写 bisect_left
int mid = (lo + hi) >>> 1;
if (tails[mid] < x) lo = mid + 1;
else hi = mid;
}
tails[lo] = x;
if (lo == size) size++;
}
return size;
}
}class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// O(n log n) 版本：tails + lower_bound 等价 bisect_left
vector<int> tails;
for (int x : nums) {
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) {
tails.push_back(x);
} else {
*it = x;
}
}
return (int)tails.size();
}
};复杂度 O(n log n) 时间、O(n) 空间。
Follow-up：LIS 是"单序列"。如果题目给两个序列，问公共子序列的最长长度呢？
4.2 LC 1143 最长公共子序列
题意：给两个字符串 text1 和 text2，返回它们的最长公共子序列（LCS）的长度。子序列要求相对次序保持，但不必连续。没有公共子序列时返回 0。
数据范围：
1 ≤ text1.length, text2.length ≤ 1000- 全为小写英文字母
示例：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：LCS 是 "ace"，长度 3。状态定义
定义 f[i][j] = text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度（约定 B，"前 i 个" / "前 j 个"）。
边界：f[0][*] = f[*][0] = 0——任一串为空时 LCS 长度为 0。
转移
考虑 f[i][j] 怎么得来。看 text1[i - 1] 和 text2[j - 1] 这两个字符：
- 相等（
text1[i - 1] == text2[j - 1]）：把它们都"用掉"，加入 LCS。f[i][j] = f[i - 1][j - 1] + 1。 - 不相等：要么不用
text1[i - 1]、要么不用text2[j - 1]，取两者最大。f[i][j] = max(f[i - 1][j], f[i][j - 1])。
为什么不考虑"两个都不用"？因为 f[i - 1][j - 1] ≤ f[i - 1][j] ≤ f[i][j]，所以"两个都不用"这个情况已经被 f[i - 1][j] 或 f[i][j - 1] 覆盖了。
填表演示
下面交互演示走 text1 = "abcde", text2 = "ace" 的关键填表步骤——金色格子是当前在算的，蓝色是它依赖的来源：
LCS("abcde", "ace") 填表演示
左上到右下逐行；相等取对角线 +1，不等取上/左的较大值
| a | c | e | ||
|---|---|---|---|---|
0 | 0 | 0 | 0 | |
| a | 0 | · | · | · |
| b | 0 | · | · | · |
| c | 0 | · | · | · |
| d | 0 | · | · | · |
| e | 0 | · | · | · |
填表方向：从左上到右下逐行扫描，因为 f[i][j] 依赖 f[i-1][j-1]、f[i-1][j]、f[i][j-1]，全在它的左上方向。
代码
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
f = [[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]:
f[i][j] = f[i - 1][j - 1] + 1
else:
f[i][j] = max(f[i - 1][j], f[i][j - 1])
return f[m][n]class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] f = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
}
}
}
return f[m][n];
}
}class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i - 1] == text2[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
}
return f[m][n];
}
};复杂度 O(mn) 时间、O(mn) 空间。
滚动数组优化到 O(n) 空间
f[i][j] 只依赖 f[i - 1][*] 和 f[i][j - 1]，即"上一行 + 当前行已填部分"。所以只需两行：
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
curr[j] = prev[j - 1] + 1
else:
curr[j] = max(prev[j], curr[j - 1])
prev, curr = curr, [0] * (n + 1)
return prev[n]空间 O(n)。可以进一步压成单行，但要小心更新顺序（需要先存 prev[j - 1]），代码反而不清晰，工程上两行版可读性更好。
Follow-up：LCS 是"两串都不修改，找最长公共"。如果允许在 s 上做"插入 / 删除 / 替换"操作把它变成 t，最少多少步？
4.3 LC 72 编辑距离
链接：LeetCode 72
题意：给两个字符串 word1 和 word2，返回将 word1 改成 word2 所需的最少操作数。允许的操作是：插入一个字符、删除一个字符、替换一个字符。
数据范围：
0 ≤ word1.length, word2.length ≤ 500- 全为小写英文字母
示例：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse → rorse （把 'h' 替换成 'r'）
rorse → rose （删除 'r'）
rose → ros （删除 'e'）状态定义
定义 f[i][j] = 把 word1[0..i-1] 改成 word2[0..j-1] 的最少操作数。约定 B。
边界：
f[0][j] = j：把空串改成长度j的字符串，需要j次插入。f[i][0] = i：把长度i的字符串改成空串，需要i次删除。
转移：三选一
考虑 f[i][j]。看最后一步操作是什么：
-
word1[i - 1] == word2[j - 1]：当前字符已经一样，不用动，f[i][j] = f[i - 1][j - 1]。 -
字符不同时，三选一：
- 替换：把
word1[i - 1]换成word2[j - 1]，前i - 1和j - 1已对齐。f[i][j] = f[i - 1][j - 1] + 1。 - 删除：把
word1[i - 1]删掉，对齐word1[0..i-2]和word2[0..j-1]。f[i][j] = f[i - 1][j] + 1。 - 插入：在
word1末尾插入word2[j - 1]，对齐word1[0..i-1]和word2[0..j-2]。f[i][j] = f[i][j - 1] + 1。
- 替换：把
三种取最小：f[i][j] = 1 + min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1])。
填表演示
走 word1 = "horse", word2 = "ros"，下面 6 步动画展示关键格——金色当前格、蓝色来源、formula 显式列出 min 取哪个：
Edit Distance("horse", "ros") 填表演示
相等取对角线；不等三选一（替换 / 删除 / 插入）
| r | o | s | ||
|---|---|---|---|---|
0 | 1 | 2 | 3 | |
| h | 1 | · | · | · |
| o | 2 | · | · | · |
| r | 3 | · | · | · |
| s | 4 | · | · | · |
| e | 5 | · | · | · |
把每一格的"来源箭头"画出来就能恢复最优操作序列——这就是 DP 路径恢复的常见做法。
代码
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
f = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
f[i][0] = i # 全删
for j in range(n + 1):
f[0][j] = j # 全插
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
f[i][j] = f[i - 1][j - 1] # 无操作
else:
f[i][j] = 1 + min(
f[i - 1][j - 1], # 替换
f[i - 1][j], # 删除
f[i][j - 1], # 插入
)
return f[m][n]class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] f = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) f[i][0] = i;
for (int j = 0; j <= n; j++) f[0][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)) {
f[i][j] = f[i - 1][j - 1];
} else {
f[i][j] = 1 + Math.min(
f[i - 1][j - 1],
Math.min(f[i - 1][j], f[i][j - 1])
);
}
}
}
return f[m][n];
}
}class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i <= m; i++) f[i][0] = i; // 全删
for (int j = 0; j <= n; j++) f[0][j] = j; // 全插
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
f[i][j] = f[i - 1][j - 1]; // 无操作
} else {
f[i][j] = 1 + min({
f[i - 1][j - 1], // 替换
f[i - 1][j], // 删除
f[i][j - 1] // 插入
});
}
}
}
return f[m][n];
}
};复杂度 O(mn) 时间、O(mn) 空间。和 LCS 一样可以滚动数组压到 O(n)。
注意"插入"和"删除"在 DP 表上是对称的——给 word1 末尾插入一个字符，等价于在 word2 末尾删一个。所以 f[i - 1][j] 和 f[i][j - 1] 二选一，两个方向。
5. 边界、易错与复杂度
索引偏移：s[i - 1] 还是 s[i]
双序列 DP 里 f[i][j] 通常表示"前 i 个字符"，所以当前字符是 s[i - 1]、t[j - 1]。新手最常踩的坑是把 s[i] 写到代码里——要么数组越界，要么少考虑了第一个字符。
口诀：DP 数组下标 i ∈ [0, m]，原始字符串下标 i - 1 ∈ [0, m - 1]。
边界初始化方向
LCS 第 0 行 / 第 0 列都是 0（空串和任何串的 LCS 是 0）。
编辑距离第 0 行是 0, 1, 2, ..., n（空串变 j 个字符要 j 次插入），第 0 列是 0, 1, 2, ..., m（i 个字符变空串要 i 次删除）。
LIS 没有"第 0 个位置"，所有 f[i] 都初始化为 1。
记错边界 → 整张表全错。写前先想清楚"f[0][*]、f[*][0] 各代表什么意思"。
严格 vs 非严格 LIS
LC 300 是严格递增（<），用 bisect_left。
如果题目改成"非严格"（≤，允许相等），用 bisect_right。LC 1671 让山形数组最少删除元素就要小心这个区别。
子数组 vs 子序列
LC 718 最长重复子数组（连续）和 LC 1143 LCS（不连续）状态转移完全不同——子数组要求连续，所以 f[i][j] 必须以 s[i-1]、t[j-1] 同时结尾，不匹配就归 0；LCS 不要求连续，不匹配也能继承上一行 / 上一列。
f[i][j] 的定义要写清楚是"结尾"还是"前 i 个"。
Python 滚动数组的更新顺序
LCS / 编辑距离压到单行 f[j] 时，从左到右更新会覆盖 f[i - 1][j - 1]（已经被新值替换）。两种解法：
- 用两行
prev和curr，写起来最清晰。 - 用单行 + 一个临时变量
pre = f[j - 1]保存对角线值，每次更新后pre = old_f_j。代码紧凑但容易出错。
工程上建议先写二维，跑通后再考虑压一维。
复杂度速查
| 题 | 时间 | 空间 |
|---|---|---|
LC 300 LIS O(n²) | O(n²) | O(n) |
LC 300 LIS O(n log n) | O(n log n) | O(n) |
| LC 1143 LCS | O(mn) | O(mn) 或 O(n) 滚动 |
| LC 72 编辑距离 | O(mn) | O(mn) 或 O(n) 滚动 |
7. 小结
序列 DP 是动态规划里入门门槛最低、但变种最多的一族。掌握这一章后能搞定 LC 上一大半的字符串 / 数组 DP 题。三件事要记牢：
- 状态定义：单序列常用"以
i结尾"（约定 A），双序列 / 子序列用"前i个"（约定 B）。状态定义决定转移和边界。 - 子数组 vs 子序列：连续的归 0，不连续的可继承。LCS 和最长重复子数组是经典对照。
- LIS 优化：朴素 DP
O(n²)，n ≥ 10⁴时上 tails + 二分O(n log n)。注意bisect_left（严格）和bisect_right（非严格）的区别。
下一节会进入划分型 DP——把序列切成若干段，每段独立最优。LC 132 分割回文串 II、LC 343 整数拆分都是这一族。划分型和序列型的区别在于"切点"成了新的枚举对象。
对应灵神题单：动态规划 · 单序列 / 双序列 / 编辑距离
进阶阅读：灵茶山艾府《序列 DP 题单》；LeetCode DP 标签 高频题