动态规划（二）：序列与区间
第二十八章：动态规划（二）— 序列与区间
上一章我们用一维 DP 和背包问题打好了地基。这一章把视野拉高：当问题涉及两个序列之间的关系或者一个序列的某段区间时，状态从一维升为二维，转移方程的结构也随之改变。
序列 DP 和区间 DP 是面试中最常考、也最容易出错的两个子类。它们有一个共同特点：状态定义中带有两个下标 i 和 j，一个是行坐标，一个是列坐标——你画出的 DP 表格就是一个矩阵。看懂这个矩阵的填充顺序，就看懂了这类题。
Level 1 · 你需要知道的
28.1 最长公共子序列（LCS）
问题定义
给定两个字符串 text1 和 text2，找出它们的最长公共子序列（Longest Common Subsequence）的长度。子序列不要求连续，但必须保持在原字符串中的相对顺序。
例如：text1 = "abcde", text2 = "ace"，LCS 是 "ace"，长度为 3。
状态定义
dp[i][j] 表示 text1[0..i-1] 与 text2[0..j-1] 的最长公共子序列长度。
注意下标偏移：dp[i][j] 对应的是两个字符串各取前 i、前 j 个字符。这样做的好处是 dp[0][*] 和 dp[*][0] 天然为 0，不需要特判。
转移方程
如果 text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # 两个字符匹配，LCS 长度 +1
否则:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # 取"去掉 text1 末尾"或"去掉 text2 末尾"的较大值
代码实现
def longest_common_subsequence(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
# dp 表格大小 (m+1) x (n+1)，第 0 行和第 0 列全为 0
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)。
回溯路径：还原 LCS 本身
光知道长度不够，面试中经常要求输出具体的 LCS 字符串。方法是从 dp[m][n] 开始，向左上方回溯：
def get_lcs(text1: str, text2: str) -> str:
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])
# 从右下角回溯
i, j = m, n
result = []
while i > 0 and j > 0:
if text1[i - 1] == text2[j - 1]:
result.append(text1[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
回溯的逻辑：
- 如果当前位置的两个字符相同，说明这个字符一定在 LCS 里，记录并向左上移动。
- 否则，走 dp 值更大的那个方向。
手动模拟
以 text1 = "ABCBDAB", text2 = "BDCAB" 为例，填完 DP 表后从右下角回溯得到 LCS = "BCAB"（长度 4）。
"" B D C A B
"" 0 0 0 0 0 0
A 0 0 0 0 1 1
B 0 1 1 1 1 2
C 0 1 1 2 2 2
B 0 1 1 2 2 3
D 0 1 2 2 2 3
A 0 1 2 2 3 3
B 0 1 2 2 3 4
28.2 最长公共子串（Longest Common Substring）
和 LCS 的区别
- 子序列（subsequence）：不要求连续。
- 子串（substring）：要求连续。
状态定义变了：dp[i][j] 表示以 text1[i-1] 和 text2[j-1] 结尾的最长公共子串长度。
转移方程
如果 text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
否则:
dp[i][j] = 0 # 一旦不匹配就归零
答案是整个 dp 表中的最大值。
def longest_common_substring(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_len = 0
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
max_len = max(max_len, dp[i][j])
# else: dp[i][j] = 0 (已经是默认值)
return max_len
关键对比
| 特性 | 最长公共子序列（LCS） | 最长公共子串 |
|---|---|---|
| 连续性 | 不要求连续 | 要求连续 |
| 不匹配时 | 取左/上的最大值 | 直接归零 |
| 答案位置 | dp[m][n] | dp 表的全局最大值 |
| 时间复杂度 | O(mn) | O(mn) |
28.3 编辑距离（Levenshtein Distance）
问题定义（LeetCode #72）
给定两个字符串 word1 和 word2，允许三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
求把 word1 转换成 word2 所需的最少操作数。
状态定义
dp[i][j] 表示 word1[0..i-1] 转换为 word2[0..j-1] 的最少操作数。
初始条件
dp[0][j] = j：空串变成长度为 j 的字符串需要 j 次插入。dp[i][0] = i：长度为 i 的字符串变成空串需要 i 次删除。
转移方程
如果 word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] # 字符相同，不需要操作
否则:
dp[i][j] = 1 + min(
dp[i-1][j], # 删除 word1[i-1]
dp[i][j-1], # 在 word1 中插入 word2[j-1]
dp[i-1][j-1] # 替换 word1[i-1] 为 word2[j-1]
)
代码实现
def min_distance(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始条件
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # 删除
dp[i][j - 1], # 插入
dp[i - 1][j - 1] # 替换
)
return dp[m][n]
手动模拟
将 "horse" 转换为 "ros"：
"" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 4 4 3
答案是 3（替换 h→r，删除 r，删除 e）。
理解三种操作
在 dp 表格中，三种操作对应三个方向：
dp[i-1][j] + 1（从上方来）= 删除 word1[i-1]dp[i][j-1] + 1（从左方来）= 插入 word2[j-1]dp[i-1][j-1] + 1（从左上方来）= 替换
这个直觉很重要：想象你在 dp 矩阵中从 (0,0) 走到 (m,n)，每一步选的方向就对应一种编辑操作。
28.4 回文子串
问题定义（LeetCode #647）
给定一个字符串 s，计算其中回文子串的数目。
状态定义
dp[i][j] 表示 s[i..j]（包含两端）是否是回文串。
转移方程
dp[i][j] = True 当且仅当:
s[i] == s[j] 且 (j - i <= 2 或 dp[i+1][j-1] == True)
j - i <= 2：长度 1（单字符）、长度 2（两个相同字符）、长度 3（首尾相同，中间任意）都直接判。- 否则需要内层子串
s[i+1..j-1]也是回文。
填表顺序
因为 dp[i][j] 依赖 dp[i+1][j-1]（行号更大，列号更小），所以我们必须从下往上、从左往右遍历，或者按子串长度从小到大遍历。
def count_substrings(s: str) -> int:
n = len(s)
dp = [[False] * n for _ in range(n)]
count = 0
# 方法一：按长度遍历
for length in range(1, n + 1): # 子串长度
for i in range(n - length + 1): # 起始位置
j = i + length - 1 # 结束位置
if s[i] == s[j] and (length <= 3 or dp[i + 1][j - 1]):
dp[i][j] = True
count += 1
return count
时间 O(n²)，空间 O(n²)。
中心扩展法（更优的常数因子）
实际面试中更常见的写法是中心扩展，空间 O(1)：
def count_substrings_expand(s: str) -> int:
n = len(s)
count = 0
def expand(left: int, right: int) -> int:
cnt = 0
while left >= 0 and right < n and s[left] == s[right]:
cnt += 1
left -= 1
right += 1
return cnt
for i in range(n):
count += expand(i, i) # 奇数长度
count += expand(i, i + 1) # 偶数长度
return count
28.5 最长回文子序列
问题定义（LeetCode #516）
给定一个字符串 s，找出其中最长回文子序列的长度。注意是子序列，不要求连续。
状态定义
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][i] = 1（单个字符就是长度为 1 的回文）。
def longest_palindrome_subseq(s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
# 从下往上、从左往右填表
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
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]
和 LCS 的关系
最长回文子序列等价于 s 和 s 的逆序的最长公共子序列。这提供了另一种解法，但直接用上面的区间 DP 更直观。
Level 2 · 你应该掌握的
28.6 区间 DP 模板
什么是区间 DP
区间 DP 的状态是 dp[i][j]，表示区间 [i, j] 的最优解。它的典型特征是：大区间的答案依赖于所有可能的"分割点"把区间切成两半的结果。
通用模板
def interval_dp(arr):
n = len(arr)
dp = [[0] * n for _ in range(n)]
# 初始化：长度为 1 的区间
for i in range(n):
dp[i][i] = base_case(i)
# 按长度从小到大枚举
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf') # 或 float('-inf')，取决于求最小还是最大
for k in range(i, j): # 枚举分割点
dp[i][j] = min(
dp[i][j],
dp[i][k] + dp[k+1][j] + cost(i, j, k)
)
return dp[0][n - 1]
三重循环：外层枚举长度，中层枚举起点，内层枚举分割点。时间 O(n³)。
28.7 矩阵链乘法
问题
给定 n 个矩阵 A₁, A₂, ..., Aₙ，其中 Aᵢ 的维度为 p[i-1] × p[i]。矩阵乘法满足结合律，不同的加括号方式导致不同的乘法次数。求最少的标量乘法次数。
状态定义
dp[i][j] = 计算矩阵 Aᵢ × Aᵢ₊₁ × ... × Aⱼ 所需的最少乘法次数。
转移方程
dp[i][j] = min over k in [i, j-1] of:
dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]
其中 p[i-1] * p[k] * p[j] 是把两个结果矩阵相乘的代价。
def matrix_chain_order(p: list) -> int:
"""
p: 维度数组，长度 n+1。矩阵 Ai 的维度为 p[i-1] x p[i]。
返回最少乘法次数。
"""
n = len(p) - 1 # 矩阵个数
# dp[i][j] 表示矩阵 i 到 j 的最少乘法次数
dp = [[0] * (n + 1) for _ in range(n + 1)]
for length in range(2, n + 1): # 子链长度
for i in range(1, n - length + 2): # 起始矩阵
j = i + length - 1 # 结束矩阵
dp[i][j] = float('inf')
for k in range(i, j): # 分割点
cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
dp[i][j] = min(dp[i][j], cost)
return dp[1][n]
# 示例：4 个矩阵，维度 [30x35, 35x15, 15x5, 5x10]
p = [30, 35, 15, 5, 10]
print(matrix_chain_order(p)) # 输出 15125
28.8 戳气球（LeetCode #312）
问题
有 n 个气球，编号 0 到 n-1。每个气球上有一个数字 nums[i]。戳破气球 i 获得 nums[left] * nums[i] * nums[right] 个硬币（left 和 right 是戳破 i 后相邻的气球）。求获得硬币的最大值。
关键洞察：逆向思考
正向思考（先戳哪个）很难定义子问题，因为戳了一个气球后边界变了。反过来想：不考虑"先戳哪个"，而是考虑"最后戳哪个"。
如果气球 k 是区间 [i, j] 中最后被戳的，那么此时 k 的左边界是 i-1，右边界是 j+1（因为 [i, j] 中其他气球都已经被戳了）。
实现
在原数组两端各加一个虚拟气球（值为 1），然后做区间 DP：
def max_coins(nums: list) -> int:
# 两端加虚拟气球
nums = [1] + nums + [1]
n = len(nums)
dp = [[0] * n for _ in range(n)]
# dp[i][j] = 戳破 (i, j) 开区间内所有气球获得的最大硬币
for length in range(2, n): # 开区间长度至少为 2 才有气球可戳
for i in range(n - length):
j = i + length
for k in range(i + 1, j): # k 是最后戳的气球
coins = nums[i] * nums[k] * nums[j]
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + coins)
return dp[0][n - 1]
注意这里 dp[i][j] 是开区间 (i, j) 的定义——即不包含 i 和 j 两端。最后戳 k 时，k 的左邻居是 i，右邻居是 j。
时间 O(n³)，空间 O(n²)。
28.9 编辑距离的空间优化
标准编辑距离用 O(mn) 空间。观察转移方程：dp[i][j] 只依赖 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]——即只需要当前行和上一行。
def min_distance_optimized(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
# 确保 word2 是较短的那个（减少空间）
if m < n:
return min_distance_optimized(word2, word1)
# 只用两行
prev = list(range(n + 1)) # 上一行
curr = [0] * (n + 1)
for i in range(1, m + 1):
curr[0] = i
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
curr[j] = prev[j - 1]
else:
curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
prev, curr = curr, prev # 滚动
return prev[n]
空间从 O(mn) 降到 O(min(m, n))。
进一步优化：单行 + 一个变量
def min_distance_one_row(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
if m < n:
return min_distance_one_row(word2, word1)
dp = list(range(n + 1))
for i in range(1, m + 1):
prev_diag = dp[0] # 保存 dp[i-1][j-1]
dp[0] = i
for j in range(1, n + 1):
temp = dp[j] # 保存 dp[i-1][j]（即将被覆盖）
if word1[i - 1] == word2[j - 1]:
dp[j] = prev_diag
else:
dp[j] = 1 + min(dp[j], dp[j - 1], prev_diag)
prev_diag = temp
return dp[n]
空间 O(min(m, n))，且只用一个数组加一个额外变量。
28.10 LCS 的 O(n log n) 优化
当两个序列中不重复（或其中一个是排列）时，LCS 问题可以转化为 LIS（最长递增子序列）问题，从 O(mn) 降到 O(n log n)。
转化思路
- 对
text2中每个字符记录它在text1中出现的位置（逆序记录，保证正确性）。 - 把所有位置拼成一个序列。
- 求这个序列的 LIS。
为什么能转化？
两个字符在 LCS 中匹配的条件是：它们在两个序列中的位置都是递增的。将 text2 的每个字符映射到 text1 中的位置后，找这些位置的最长递增子序列，就等价于找 LCS。
import bisect
def lcs_via_lis(text1: str, text2: str) -> int:
"""
当字符可能重复时的通用做法。
将 LCS 问题转化为 LIS 问题。
"""
# 记录 text1 中每个字符出现的位置（逆序）
from collections import defaultdict
pos = defaultdict(list)
for i in range(len(text1) - 1, -1, -1):
pos[text1[i]].append(i)
# 构造序列：text2 中每个字符在 text1 中的位置
sequence = []
for char in text2:
if char in pos:
sequence.extend(pos[char])
# 对 sequence 求 LIS（patience sorting）
tails = []
for num in sequence:
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
tails.append(num)
else:
tails[idx] = num
return len(tails)
当两个序列长度接近且字符集较小时，这个方法比 O(mn) 快得多。
Level 3 · 你会因此与众不同
28.11 编辑距离的历史
编辑距离由苏联数学家 Vladimir Levenshtein 于 1965 年在论文《Binary codes capable of correcting deletions, insertions, and reversals》中首次定义。他研究的原始动机是信息论中的纠错码——如果一条信息在传输中发生了字符的插入、删除或替换，接收方需要知道原始信息和损坏信息之间"差了多远"。
尽管 Levenshtein 定义了这个距离度量，他并没有给出高效的算法。第一个 O(mn) 的动态规划算法由 Robert Wagner 和 Michael Fischer 于 1974 年在论文《The String-to-String Correction Problem》中提出，因此有时也称为 Wagner-Fischer 算法。
28.12 编辑距离在 NLP 和生物信息学中的应用
拼写纠错
最早的拼写纠错系统（1960-70年代）就基于编辑距离。给定一个拼写错误的单词，在字典中找编辑距离最小的词作为候选。Peter Norvig 写过一个经典的 21 行 Python 拼写纠错器，核心就是编辑距离为 1 和 2 的候选生成。
现代拼写纠错使用更复杂的模型（如 noisy channel model），但编辑距离仍然是基础组件。
DNA 序列比对
生物信息学中的序列比对（sequence alignment）本质上是编辑距离的变体。Needleman-Wunsch 算法（1970）做全局比对，Smith-Waterman 算法（1981）做局部比对。两者都是 O(mn) 的 DP 算法，区别在于：
- Needleman-Wunsch：初始化和转移方程与标准编辑距离几乎相同，但使用评分矩阵（substitution matrix）代替简单的 0/1 代价。
- Smith-Waterman：允许从任何位置开始和结束，dp 值不会变负（用
max(0, ...)截断），最终答案是 dp 表中的全局最大值而非 dp[m][n]。
BLAST（Basic Local Alignment Search Tool）是生物信息学中最常用的工具，它本质上是 Smith-Waterman 的启发式加速版本。
自然语言处理中的应用
- 机器翻译评价：WER（Word Error Rate）就是词级别的编辑距离除以参考句子的长度。
- 信息抽取：实体匹配时用编辑距离判断两个名字是否指同一个实体（如 "Jon Snow" vs "John Snow"）。
- 模糊搜索：数据库中
SOUNDEX、LEVENSHTEIN()函数的底层实现。
28.13 Myers diff 算法
Git diff 的核心
当你运行 git diff 时，Git 使用的是 Eugene Myers 于 1986 年发表的论文《An O(ND) Difference Algorithm and Its Variations》中的算法。这个算法的时间复杂度是 O(ND)，其中 N 是两个文件的总长度，D 是最小编辑距离（diff 的大小）。
核心思想
Myers 算法把 diff 问题转化为图的最短路径问题：
- 构造一个 (m+1) × (n+1) 的编辑图（edit graph）。
- 从 (0,0) 到 (m,n) 的每条路径对应一种编辑方式。
- 水平移动 = 删除，垂直移动 = 插入，对角线移动 = 保持（不计代价）。
- 目标：找从 (0,0) 到 (m,n) 的路径，使非对角线移动最少。
算法流程
对于 d = 0, 1, 2, ...:
对于每个对角线 k = -d, -d+2, ..., d:
尽可能沿对角线前进（贪心：匹配的字符不算代价）
如果到达 (m, n)，返回 d
当两个文件差异很小时（D 很小），算法近乎线性。这就是为什么 git diff 通常很快——大多数提交只改了几行。
与标准 DP 的关系
Myers 算法本质上是在 Levenshtein DP 的编辑图上做 BFS，但利用了对角线上可以免费移动的特性。它等价于"只有插入和删除两种操作的编辑距离"（不允许替换），这正是 diff 需要的：一行要么保留、要么删除、要么插入。
28.14 Wagner-Fischer 算法的形式化
Wagner 和 Fischer 在 1974 年的论文中做了以下贡献：
-
证明了最优子结构：如果从 word1 到 word2 的最优编辑序列的最后一步是操作 X，那么去掉最后一步后，前面的部分一定也是最优的。
-
证明了正确性：通过归纳法证明 dp[i][j] 确实等于 word1[0..i-1] 到 word2[0..j-1] 的最小编辑距离。
-
推广了代价模型：允许不同操作有不同的代价 w(a→b)，只要代价函数满足度量性质（非负、对称、三角不等式）。
28.15 区间 DP 与最优二叉搜索树（Knuth 优化）
最优二叉搜索树问题
给定 n 个有序的关键字 k₁ < k₂ < ... < kₙ，每个关键字 kᵢ 被搜索的概率为 pᵢ。构造一棵 BST，使得搜索的期望代价最小。
这是一个经典的区间 DP 问题：
dp[i][j] = 以 ki, ..., kj 为关键字的最优 BST 的期望搜索代价
dp[i][j] = min over r in [i, j] of:
dp[i][r-1] + dp[r+1][j] + sum(p[i..j])
朴素实现是 O(n³)。但 Donald Knuth 在 1971 年证明了一个关键性质：设 root[i][j] 是 dp[i][j] 对应的最优根节点，则：
root[i][j-1] <= root[i][j] <= root[i+1][j]
即最优分割点具有单调性。利用这个性质，内层循环不再需要遍历所有 k，总时间从 O(n³) 降到 O(n²)。
Knuth 优化的适用条件
区间 DP 的代价函数 w(i, j) 满足以下两个条件时可以应用 Knuth 优化：
- 区间包含单调性（monotone on the lattice of intervals）：
w(a, c) + w(b, d) <= w(a, d) + w(b, c)，对所有a <= b <= c <= d。 - 凸不等式（quadrangle inequality）：
w(i, j)满足四边形不等式。
满足时，最优分割点 root[i][j] 单调，可以将 O(n³) 优化到 O(n²)。
def optimal_bst(p: list, n: int) -> float:
"""
p[1..n]: 搜索概率
返回最小期望搜索代价
"""
# prefix_sum[i] = p[1] + ... + p[i]
prefix_sum = [0] * (n + 2)
for i in range(1, n + 1):
prefix_sum[i] = prefix_sum[i - 1] + p[i]
def w(i, j):
return prefix_sum[j] - prefix_sum[i - 1]
dp = [[0.0] * (n + 2) for _ in range(n + 2)]
root = [[0] * (n + 2) for _ in range(n + 2)]
# 初始化：长度为 1
for i in range(1, n + 1):
dp[i][i] = p[i]
root[i][i] = i
# 按长度填表
for length in range(2, n + 1):
for i in range(1, n - length + 2):
j = i + length - 1
dp[i][j] = float('inf')
# Knuth 优化：分割点范围缩小
for r in range(root[i][j - 1], root[i + 1][j] + 1):
cost = dp[i][r - 1] + dp[r + 1][j] + w(i, j)
if cost < dp[i][j]:
dp[i][j] = cost
root[i][j] = r
return dp[1][n]
Level 4 · 实战陷阱与高频面试题
28.16 编辑距离的边界条件陷阱
编辑距离看起来简单，但在面试中很多人在边界条件上犯错：
陷阱一：忘记初始化第 0 行和第 0 列
# 错误写法：忘了初始化
dp = [[0] * (n + 1) for _ in range(m + 1)]
# dp[i][0] 和 dp[0][j] 都是 0，这是错的！
# 正确写法
for i in range(m + 1):
dp[i][0] = i # 删除 i 个字符
for j in range(n + 1):
dp[0][j] = j # 插入 j 个字符
陷阱二：空串处理
当 word1 或 word2 为空时，答案就是另一个字符串的长度。如果你的代码特判了 if not word1: return len(word2)，那没问题。但如果你依赖 DP 表格，必须确保初始化正确覆盖了这种情况。
陷阱三：下标偏移
dp[i][j] 对应 word1[0..i-1] 和 word2[0..j-1]。在写转移方程时，比较的是 word1[i-1] 和 word2[j-1]，不是 word1[i] 和 word2[j]。这个 off-by-one 错误非常常见。
28.17 LCS 与编辑距离的关系
这是一个重要的数学等式：
设
word1长度为 m，word2长度为 n，它们的 LCS 长度为 L，只允许插入和删除（不允许替换）的编辑距离为 d，则：d = m + n - 2L
证明
LCS 中的 L 个字符是"不需要动"的。word1 中不在 LCS 中的 m - L 个字符需要删除，word2 中不在 LCS 中的 n - L 个字符需要插入。总操作数 = (m - L) + (n - L) = m + n - 2L。
实际意义
- 如果只允许插入和删除（不允许替换），编辑距离 = m + n - 2 × LCS。
- 如果允许替换，Levenshtein 距离 <= m + n - 2 × LCS（因为一次替换可以代替一次删除 + 一次插入）。
LeetCode #583（Delete Operation for Two Strings）就直接考这个关系。
28.18 面试高频序列 DP 题
不同的子序列（LeetCode #115）
给定字符串 s 和 t，计算在 s 中有多少个不同的子序列等于 t。
def num_distinct(s: str, t: str) -> int:
m, n = len(s), len(t)
# dp[i][j] = s[0..i-1] 的子序列中等于 t[0..j-1] 的个数
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始条件：t 为空时，任何 s 都有一个空子序列匹配
for i in range(m + 1):
dp[i][0] = 1
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = dp[i - 1][j] # 不选 s[i-1]
if s[i - 1] == t[j - 1]:
dp[i][j] += dp[i - 1][j - 1] # 选 s[i-1] 匹配 t[j-1]
return dp[m][n]
交错字符串（LeetCode #97）
给定三个字符串 s1、s2、s3，判断 s3 是否可以由 s1 和 s2 交错组成。
def is_interleave(s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
# dp[i][j] = s1 前 i 个 + s2 前 j 个能否交错组成 s3 前 i+j 个
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, m + 1):
dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
for j in range(1, n + 1):
dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = (
(dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or
(dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
)
return dp[m][n]
正则表达式匹配（LeetCode #10）
实现支持 . 和 * 的正则表达式匹配。. 匹配任意单个字符，* 匹配零个或多个前面的元素。
def is_match(s: str, p: str) -> bool:
m, n = len(s), len(p)
# dp[i][j] = s[0..i-1] 是否匹配 p[0..j-1]
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
# 初始化：s 为空，p 中 x* 可以匹配零次
for j in range(2, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 2]
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
# * 匹配零次前面的字符
dp[i][j] = dp[i][j - 2]
# * 匹配一次或多次
if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
dp[i][j] = dp[i][j] or dp[i - 1][j]
elif p[j - 1] == '.' or p[j - 1] == s[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
关键点： * 的两种选择——匹配零次（向左跳两格 dp[i][j-2]）和匹配一次以上（向上 dp[i-1][j]，因为 * 还可以继续匹配）。
通配符匹配（LeetCode #44）
实现支持 ? 和 * 的通配符匹配。? 匹配任意单个字符，* 匹配任意字符串（包括空串）。
def is_match_wildcard(s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
# p 的前缀全是 * 时可以匹配空串
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
else:
break
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
# * 匹配空 (dp[i][j-1]) 或 匹配当前字符 (dp[i-1][j])
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif p[j - 1] == '?' or p[j - 1] == s[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
正则匹配 vs 通配符匹配的区别：
| 特性 | 正则（#10） | 通配符（#44） |
|---|---|---|
* 含义 |
重复前一个字符 0 或多次 | 匹配任意字符串 |
* 独立性 |
不能独立存在，必须跟在字符后面 | 独立存在 |
| 初始化 | dp[0][j]: 看 x* 模式 | dp[0][j]: 看 * 前缀 |
28.19 股票买卖系列（状态机 DP）
股票买卖系列是经典的状态机 DP 题。核心思路：定义状态不仅包含天数 i，还包含当前是否持股、已完成的交易次数等额外维度。
通用框架
定义：
dp[i][k][0]= 第 i 天结束，最多完成 k 笔交易，不持股时的最大利润dp[i][k][1]= 第 i 天结束，最多完成 k 笔交易，持股时的最大利润
转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
# 昨天就不持股 # 今天卖出
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
# 昨天就持股 # 今天买入（用掉一次交易机会）
买卖股票 II（LeetCode #122）—— 不限次数
k = infinity，k 和 k-1 没有区别：
def max_profit_ii(prices: list) -> int:
n = len(prices)
# dp_hold: 持有股票时的最大利润
# dp_cash: 不持有股票时的最大利润
dp_cash, dp_hold = 0, -prices[0]
for i in range(1, n):
dp_cash = max(dp_cash, dp_hold + prices[i])
dp_hold = max(dp_hold, dp_cash - prices[i])
return dp_cash
买卖股票 III（LeetCode #123）—— 最多两笔
def max_profit_iii(prices: list) -> int:
# 4 个状态：第一次买、第一次卖、第二次买、第二次卖
buy1 = buy2 = -float('inf')
sell1 = sell2 = 0
for price in prices:
buy1 = max(buy1, -price)
sell1 = max(sell1, buy1 + price)
buy2 = max(buy2, sell1 - price)
sell2 = max(sell2, buy2 + price)
return sell2
买卖股票 IV（LeetCode #188）—— 最多 k 笔
def max_profit_iv(k: int, prices: list) -> int:
n = len(prices)
if not prices or k == 0:
return 0
# 如果 k >= n//2，等于不限次数
if k >= n // 2:
return sum(max(prices[i + 1] - prices[i], 0) for i in range(n - 1))
# dp[j][0]: 完成最多 j 笔交易且不持股
# dp[j][1]: 完成最多 j 笔交易且持股
dp = [[0, -float('inf')] for _ in range(k + 1)]
for price in prices:
for j in range(1, k + 1):
dp[j][0] = max(dp[j][0], dp[j][1] + price)
dp[j][1] = max(dp[j][1], dp[j - 1][0] - price)
return dp[k][0]
含冷冻期（LeetCode #309）
卖出后第二天不能买入。增加一个"冷冻"状态：
def max_profit_cooldown(prices: list) -> int:
n = len(prices)
if n <= 1:
return 0
# 三个状态：持股、不持股(非冷冻)、冷冻期
hold = -prices[0]
cash = 0
frozen = 0
for i in range(1, n):
new_hold = max(hold, cash - prices[i]) # 买入只能从 cash（非冷冻）转移
new_cash = max(cash, frozen) # 保持不持股，或从冷冻恢复
new_frozen = hold + prices[i] # 卖出进入冷冻
hold, cash, frozen = new_hold, new_cash, new_frozen
return max(cash, frozen)
状态机图解
买入
cash ──────────► hold
▲ │
│ 解冻 │ 卖出
│ ▼
frozen ◄────────── (卖出时转移)
28.20 总结：序列与区间 DP 的思维导图
序列 DP
├── 两个序列
│ ├── LCS：dp[i][j] = 前 i 和前 j 的 LCS 长度
│ ├── 编辑距离：dp[i][j] = word1 前 i 转成 word2 前 j 的最小代价
│ ├── 交错字符串：dp[i][j] = s1 前 i + s2 前 j 能否组成 s3 前 i+j
│ └── 正则/通配符匹配：dp[i][j] = s 前 i 是否匹配 p 前 j
├── 单个序列
│ ├── 回文子串：dp[i][j] = s[i..j] 是否回文
│ ├── 最长回文子序列：dp[i][j] = s[i..j] 中最长回文子序列长度
│ └── 不同的子序列：dp[i][j] = s 前 i 中有多少子序列等于 t 前 j
└── 状态机 DP
└── 股票买卖：dp[i][k][state] = 第 i 天、k 次交易、状态 state 下的最大利润
区间 DP
├── 模板：dp[i][j] = 区间 [i,j] 的最优解，枚举分割点 k
├── 矩阵链乘法
├── 戳气球：开区间定义，逆向思考
├── 最优 BST + Knuth 优化：O(n³) → O(n²)
└── 回文相关（也是区间 DP）
面试建议
- 拿到序列 DP 题，先想清楚
dp[i][j]的精确含义——是"前 i 个"还是"以第 i 个结尾"。 - 区间 DP 的标志：问题涉及"一段连续区间"的最优解，且大区间可以通过分割成小区间来求解。
- 正则/通配符匹配是编辑距离的"变体"——本质都是两个序列的 DP，只是转移规则不同。
- 股票系列看似不是序列 DP，实则是标准的状态机 DP。把所有可能的"状态"（持股/不持股/冷冻/交易次数）画出来，转移自然就清楚了。