题目定位
这是最标准的序列 DP：状态由两个字符串前缀共同决定，转移则取决于当前字符是否匹配。
关键观察
字符相等时取对角线加一；否则就在“跳过左边一个字符”和“跳过右边一个字符”之间取较优。
目标复杂度
O(mn) / O(mn)
这题的解法思路怎么拆
1
这是最标准的序列 DP：状态由两个字符串前缀共同决定，转移则取决于当前字符是否匹配。
2
字符相等时取对角线加一；否则就在“跳过左边一个字符”和“跳过右边一个字符”之间取较优。
3
先用自然语言命名状态。
4
列出哪些决策会转移到这个状态。
参考实现
Python# Generic pattern template
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
dp[i] = transition(dp, i)
# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = transition(dp, i, j)
常见坑点
warning
把子串直觉错误套到子序列上。
warning
转移时不必要地同时跳过两边字符。
高频追问
如果还要恢复出一个具体序列，该怎么做？
编辑距离和这张状态表有什么联系？
继续刷相关题
先把 动态规划 这个模式刷成体系，再去做更难变体。