引言 (Introduction)
前面三篇文章中，DP 的状态都在一个维度上展开：一维线性、二维网格、一维容量的背包。但从本篇开始，DP 将面对一种更复杂的场景：两个序列之间的对齐与比较。
本文是本系列第四篇，聚焦于双串 DP（LCS、编辑距离）与单串子序列 DP（LIS、回文子串）。这些问题构成了字符串算法和生物信息学（序列比对）的算法基础，也是面试中 DP 题目的高频来源。
1. LeetCode 1143：最长公共子序列（LCS）
题目：给定两个字符串 text1 和 text2，求它们的最长公共子序列（Longest Common Subsequence）的长度。子序列不要求在原字符串中连续。
1.1 状态定义
$dp[i][j]$：text1 的前 $i$ 个字符与 text2 的前 $j$ 个字符的 LCS 长度。
转移方程：
$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } text1[i-1] = text2[j-1] \\ \max(dp[i-1][j],\ dp[i][j-1]) & \text{otherwise} \end{cases}$$直觉：两个字符相等时，必然可以加入 LCS（从左上角转移）。不相等时，至少丢弃其中一个字符，取两者中较长的。
1.2 完整代码
from typing import List
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
# dp[i][j] 对应 text1[:i] 和 text2[:j]
dp: List[List[int]] = [[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(\min(m, n))$（滚动数组保留上一行）。
1.3 从 dp 表反推 LCS 字符串
from typing import List
def reconstruct_lcs(text1: str, text2: str, dp: List[List[int]]) -> str:
"""从填充好的 dp 表反推出一个 LCS 字符串"""
i, j = len(text1), len(text2)
lcs_chars: List[str] = []
while i > 0 and j > 0:
if text1[i - 1] == text2[j - 1]:
lcs_chars.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(lcs_chars))
1.4 LCS 的广泛应用
LCS 不仅仅是一道面试题。它在实际工程中拥有众多变体：Unix diff 命令、Git 的文件差异比较、基因序列比对（Needleman-Wunsch 算法）、拼写纠错等。理解了 LCS，就理解了序列对齐问题的核心建模思想。
2. LeetCode 300：最长递增子序列（LIS）
题目：给定整数数组 nums，求最长严格递增子序列的长度。
2.1 $O(n^2)$ 的 DP 解法
定义 $dp[i]$ 为以 $nums[i]$ 结尾的最长递增子序列长度。转移：
$$dp[i] = \max_{j < i,\ nums[j] < nums[i]}(dp[j] + 1)$$from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp: List[int] = [1] * n # 每个元素自身构成长度为 1 的 LIS
ans = 1
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
ans = max(ans, dp[i])
return ans
2.2 $O(n \log n)$ 的贪心 + 二分优化
维护一个数组 tails，tails[k] 表示长度为 $k+1$ 的递增子序列的最小可能尾元素。遍历 nums 时，对每个数用二分查找确定它在 tails 中的位置：
- 如果它比
tails中所有元素都大，追加到末尾（LIS 长度 +1）。 - 否则，替换第一个 $\ge$ 它的元素（降低对应长度的尾元素值，为后续更大的数创造空间）。
import bisect
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
tails: List[int] = []
for x in nums:
idx = bisect.bisect_left(tails, x) # 第一个 >= x 的位置
if idx == len(tails):
tails.append(x)
else:
tails[idx] = x
return len(tails)
复杂度：时间 $O(n \log n)$，空间 $O(n)$。
2.3 为什么 $O(n \log n)$ 可行？
tails 数组始终保持递增（证明：每次替换只降低值，不破坏递增性）。二分查找的前提得到满足。这个优化是 DP + 贪心的经典结合——DP 定义了状态语义，贪心（二分替换）加速了转移。这提醒我们：算法设计不存在绝对的方法论边界，真正的问题求解往往是多种思想的融合。
3. LeetCode 72：编辑距离
题目：给定两个单词 word1 和 word2，求将 word1 转换为 word2 的最少操作数。允许三种操作：插入一个字符、删除一个字符、替换一个字符。
3.1 状态定义与转移
$dp[i][j]$：word1 的前 $i$ 个字符转换为 word2 的前 $j$ 个字符的最少操作数。
直觉：两个字符相同 → 不需要操作。不同 → 在删除（跳过 $i$，从 $i-1$ 来）、插入（跳过 $j$，从 $j-1$ 来）、替换（两个都跳过，加一次操作）中取最小值。
3.2 完整代码
from typing import List
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp: List[List[int]] = [[0] * (n + 1) for _ in range(m + 1)]
# 边界：将空串转为 word2[:j] 需要 j 次插入
for j in range(1, n + 1):
dp[0][j] = j
# 边界：将 word1[:i] 转为空串需要 i 次删除
for i in range(1, m + 1):
dp[i][0] = i
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]
复杂度：时间 $O(mn)$，空间 $O(mn)$。
3.3 LCS 与编辑距离的关系
编辑距离和 LCS 都是双串 DP，状态表格结构相同（$m \times n$），但转移方程的语义不同：
| 问题 | 相等时的转移 | 不等时的转移 | 目标 |
|---|---|---|---|
| LCS | $dp[i-1][j-1] + 1$ | $\max(dp[i-1][j], dp[i][j-1])$ | 最大化公共部分 |
| 编辑距离 | $dp[i-1][j-1]$（无操作） | $1 + \min($删, 插, 换$)$ | 最小化差异 |
两者对偶：LCS 问「保留多少相同」，编辑距离问「消除多少不同」。实际上，只允许删除和插入的编辑距离（不允许替换）等价于 $m + n - 2 \times LCS$。
4. LeetCode 5：最长回文子串
题目：给定字符串 s，求最长的回文子串。
4.1 区间 DP 建模
这是区间 DP 的入门题。状态定义：$dp[i][j]$ 表示 s[i:j+1] 是否为回文串。
即两端字符相等，且去掉两端后内层也是回文（或子串长度 $\le 2$，此时两字符相等即回文）。
填表顺序：按子串长度从小到大填表（因为长区间依赖短区间）。
4.2 完整代码
from typing import List
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n < 2:
return s
dp: List[List[bool]] = [[False] * n for _ in range(n)]
start, max_len = 0, 1
# 长度为 1 的子串都是回文
for i in range(n):
dp[i][i] = True
# 按长度从 2 到 n 填表
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
if length == 2 or dp[i + 1][j - 1]:
dp[i][j] = True
if length > max_len:
start, max_len = i, length
return s[start:start + max_len]
复杂度：时间 $O(n^2)$，空间 $O(n^2)$。
4.3 区间 DP 的填表模式
区间 DP 的核心特征是状态由区间长度定义，而非固定的索引方向。填表始终按 length 从小到大进行：
for length in range(2, n + 1): # 外层：长度
for i in range(n - length + 1): # 内层：左端点
j = i + length - 1 # 右端点
# 转移方程依赖 [i+1][j-1]（更短的区间，已经计算完毕）
这个模板适用于石子合并、戳气球、矩阵链乘等一系列区间 DP 问题。
5. 字符串 DP 的统一视角
回顾四道题的建模共性：
| 题目 | 状态维度 | 状态定义 | 转移来源 | 复杂度 |
|---|---|---|---|---|
| 1143 LCS | 双串 | $dp[i][j]$：前 $i$ 与前 $j$ 的 LCS 长度 | 左上 / 左 / 上 | $O(mn)$ |
| 300 LIS | 单串 | $dp[i]$：以 $i$ 结尾的 LIS 长度 | 前驱 $j$（$O(n)$ / $O(\log n)$） | $O(n^2)$ / $O(n \log n)$ |
| 72 编辑距离 | 双串 | $dp[i][j]$：前 $i$ 转前 $j$ 的最小操作 | 左上 / 左 / 上 | $O(mn)$ |
| 5 回文子串 | 单串区间 | $dp[i][j]$：$s[i:j+1]$ 是否回文 | 内部 $[i+1][j-1]$ | $O(n^2)$ |
双串 DP 的统一模板：
- $dp[i][j]$ 表示串 1 前 $i$ 个和串 2 前 $j$ 个的某种关系。
- 转移通常涉及 $i-1$、$j-1$、$i-1,j-1$ 三个方向。
- 填表顺序始终是 $i$ 从 $1$ 到 $m$、$j$ 从 $1$ 到 $n$。
区间 DP 的统一模板：
- $dp[i][j]$ 表示区间 $[i, j]$ 上的某种性质。
- 按
length从小到大填表。 - 转移通常依赖 $[i+1][j]$、$[i][j-1]$、$[i+1][j-1]$。
结论 (Conclusion)
本文完成了 DP 在序列/字符串领域的四项核心建模：
- LCS：双串 DP 的经典范式——相等则共享，不等则丢弃。
- LIS：从 $O(n^2)$ 的 DP 到 $O(n \log n)$ 的 DP+贪心，展示了算法融合的力量。
- 编辑距离：与 LCS 互为对偶，覆盖了双串比较的「差异最小化」视角。
- 回文子串：区间 DP 的入门，按长度填表是区间 DP 的通用套路。
下一篇预览：本系列的收官之作——状态压缩、树形 DP、区间 DP 进阶，以及全系列复盘对照表（LeetCode 337、139、152）。