这段时间集中刷力扣，动态规划专题一路做下来，0226这道题卡了我将近一个晚上。后来我在刷题笔记里给它专门标了个“必考题”，原因很简单——它把二维动态规划里最难讲清楚的三个东西一次全暴露了：状态怎么定义、边界怎么初始化、空间怎么优化。
先声明一下，这个 0226 是我自己在刷题笔记里排的编号，跟力扣官方题号不是一回事。官方题号不重要，重要的是这类题背后的方法论。为了方便叙述，我把题目还原成最经典的那个场景：给定两个字符串 s 和 t，可以对 s 做三种操作，插入一个字符、删除一个字符、替换一个字符，问把 s 变成 t 最少需要多少次操作。
这就是很多人面试时遇到的“编辑距离”问题。它解决的现实需求很直观：文本 diff 工具里要对比两个文件差了几行、拼写检查软件要猜你打错的那个词最接近哪个正确词、甚至基因序列比对里也能看到它的影子。所以不管你是刚开始学 DP 的小白，还是准备面试想系统刷一遍高频题的老手，把这道题吃透都特别值。
1. 题目拆解与 DP 识别：为什么第一反应该想到动态规划
1.1 先别急着写代码，把操作含义盘明白
很多人一看到“最少操作次数”这种表述，脑子里就开始倒腾贪心策略：是不是每次挑最优的操作就行？我也试过，结果发现贪心在这里根本站不住脚。给你一个很简单的反例：s = "ab"，t = "ba"。如果只看当前字符，s[0] 是 'a'，t[0] 是 'b'，你可能会想把 'a' 替换成 'b'，然后第二个字符再把 'b' 替换成 'a'，一共 2 次替换。最优解其实只需要 2 次？也不是，其实是 2 次，但这个例子里替换和“删掉一个再插入一个”效果一样，问题在于当字符串更长时，某个局部看起来最优的操作，可能会让后面的字符全部错位，最后反而多花好几步。
这个现象背后藏着一个关键结构：当前这一步怎么选，会影响后面一系列步骤的状态。什么时候会出现这种事？当问题可以被拆成规模更小的子问题，而且子问题之间有重叠时，就是典型的动态规划信号。
1.2 最优子结构和重叠子问题，两个信号一个都不能少
编辑距离为什么具备这两个信号？我们盯着 s 和 t 的最后一个字符看。如果 s 的最后一位和 t 的最后一位已经相等了，那实际上我们只需要解决前面部分的转换问题，最后一个字符不用动。如果不等，我们有三条路：
- 替换 s 的最后一个字符，让它等于 t 的最后一个字符，然后解决前面部分的转换；
- 删除 s 的最后一个字符，然后解决剩下来的 s 前缀和完整 t 之间的转换；
- 在 s 的末尾插入一个字符，让它去匹配 t 的最后一位，然后解决完整 s 和新 t 前缀之间的转换；
你看，不管走哪条路，最终都落回到“把某个前缀变成某个前缀”这个更小的问题上，而且不同的选择路径会反复遇到同样的子问题。我拍脑袋算了算，如果纯递归去解，每次分 3 个叉，深度是 m+n，整体复杂度直接指数爆炸。但用动态规划把这些子问题的答案存下来，每个子问题只算一次，复杂度瞬间就降下来了。
这就是我反复跟人强调的那个判断标准——不是因为题目里带个“最少”就是 DP，而是因为大问题能拆小、小问题互相重叠，这才是 DP 的主场。
2. 状态定义与转移方程：把“直觉”翻成公式
2.1 dp[i][j] 为什么这样定义
动态规划最核心的一步，就是给状态一个精确的含义。我见过太多人卡在这一步，状态定义得含糊，后面全乱。这题我建议这样定义：
dp[i][j] 表示字符串 s 的前 i 个字符，转换成字符串 t 的前 j 个字符，需要的最少操作次数。
注意，这里说的是“前 i 个”和“前 j 个”，不是“第 i 个”和“第 j 个”。这个细节极其重要。用“前 i 个”而不是“下标到 i”，可以让我们在 i = 0 或 j = 0 的时候直接对应“空字符串”这个状态，处理边界特别自然。如果定义成“第 i 个字符到第 j 个字符”，你还要单独处理空串的情况，状态下标也会绕来绕去。
拿一个具体例子试一下。s = "horse"，t = "ros"。dp[3][2] 表示 "hor" 变成 "ro" 的最少步数。我们最终要的答案就是 dp[5][3]。
2.2 转移方程的三种来源，一次讲透
现在来推导核心的转移方程。假设我们已经算出了所有比 (i, j) 规模更小的子问题，想要算 dp[i][j]。分两种情况：
情况一：s[i-1] == t[j-1]
最后一个字符已经相等，不需要额外操作。当前问题直接继承 dp[i-1][j-1]。这里很多人会犯迷糊，想着“是不是还可以删掉这个相等的字符再插回来，也能得到同样结果？”理论上可以，但步数会多 2 步，最小步数一定不会选它。所以直接用继承。
情况二：s[i-1] != t[j-1]
这时候必须做一次操作。三个选择对应三次子问题：
- 替换：把 s[i-1] 改成 t[j-1]，那么前面 i-1 个字符要变成前面 j-1 个字符，代价是 dp[i-1][j-1] + 1；
- 删除：把 s[i-1] 删掉，那么剩下的前 i-1 个字符要变成完整的前 j 个字符，代价是 dp[i-1][j] + 1；
- 插入：在 s 的末尾补一个 t[j-1]，让新字符去匹配 t 的最后一个字符，原 s 的前 i 个字符要变成 t 的前 j-1 个字符，代价是 dp[i][j-1] + 1。
三者取最小值。
这三个下标关系我建议不要死记，每次写的时候自己画一画字符串就清楚了。我最开始学的时候反复搞混“插入对应 dp[i][j-1] 还是 dp[i-1][j]”，后来找到一个记忆方法：你插入的是 s 这边的字符，但匹配的是 t 的最后一个字符，所以 t 的规模变小了，也就是 j 变成 j-1。同理，删除删的是 s 的字符，s 的规模变小，也就是 i 变成 i-1。
2.3 边界初始化：空串到非空串，只有一条路
边界情况是整个二维表中的第一行和第一列。
dp[0][j] 表示空字符串 s 变成 t 的前 j 个字符，能怎么办？只能一个一个插入，所以 dp[0][j] = j。
dp[i][0] 表示 s 的前 i 个字符变成空字符串，只能一个一个删除，所以 dp[i][0] = i。
这两个边界看似简单，但如果漏了，后面整张表都会算错。我经常看到有人给 dp 数组开好了 (m+1) x (n+1) 的尺寸，却忘记给第一行第一列赋值，结果算出来的答案全偏。
为了让你彻底看懂，我手算一个完整的例子。s = "horse"，t = "ros"，表格初始化之后长这样：
| dp | 空 | r | o | s |
|---|---|---|---|---|
| 空 | 0 | 1 | 2 | 3 |
| h | 1 | |||
| o | 2 | |||
| r | 3 | |||
| s | 4 | |||
| e | 5 |
逐行填。第一行处理完你会发现，整个转移过程就是把“当前字符是否相等”这个判断，翻译成一个 min 运算。填完之后右下角的 dp[5][3] 是 3，也就是说 "horse" 变成 "ros" 最少需要 3 次操作：h 替换成 r、删除 e、删除 o 前面的一个？具体路径是什么大家填完表可以自己倒推一下。
3. 代码实现与空间优化：从二维变一维，到底在优化什么
3.1 基础版：先写二维，把逻辑跑通
我写题一直有个习惯：先把最直白的版本写正确，再谈优化。直接一上来写一维滚动数组，很容易把自己绕晕。先看二维版本：
def min_distance(s: str, t: str) -> int: m, n = len(s), len(t) 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 s[i - 1] == t[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = min( dp[i - 1][j - 1], # 替换 dp[i - 1][j], # 删除 dp[i][j - 1] # 插入 ) + 1 return dp[m][n]迭代顺序是外层 i、内层 j，从左到右、从上到下。为什么这个顺序对？因为 dp[i][j] 依赖的是左上角 dp[i-1][j-1]、正上方 dp[i-1][j]、正左方 dp[i][j-1]，这三个位置在当前格子被计算之前，都已经被算过了。只要保持这个双重循环，依赖关系就不会被破坏。
时间复杂度 O(m * n)，空间复杂度也是 O(m * n)。这个版本已经能通过力扣的测试。但面试官通常会追问一句：能不能把空间省下来？
3.2 滚动数组优化：只保留上一行，但左上角要单独存
观察一下转移方程，你算第 i 行的时候，其实只需要第 i-1 行的数据，更早的行用不到了。所以可以用一个长度为 n+1 的一维数组，反复更新。这就是经典的“滚动数组”思路。
但这里面藏着一个最常见的坑：dp[i-1][j-1] 即左上角的值，在滚动更新过程中很容易被覆盖掉。
你想，我们用一维数组时，dp[j] 同时承担了“上一行的第 j 列”和“当前行的第 j 列”两个角色。如果直接在一行内从左往右刷新 dp[j]，那么当你算 dp[j] 时，dp[j-1] 已经被刷新成当前行的值了，不再代表左上方。解决办法是：在更新 dp[j] 之前，用一个临时变量把旧值存下来，也就是上一行的 dp[j-1]。
我当时的实现长这样：
def min_distance_scroll(s: str, t: str) -> int: m, n = len(s), len(t) dp = [j for j in range(n + 1)] for i in range(1, m + 1): prev = dp[0] # 上一行的 dp[i-1][0] dp[0] = i # 当前行的 dp[i][0] for j in range(1, n + 1): temp = dp[j] # 保存未更新前的 dp[j]，即 dp[i-1][j] if s[i - 1] == t[j - 1]: dp[j] = prev # 这里的 prev 就是 dp[i-1][j-1] else: dp[j] = min(prev, dp[j], dp[j - 1]) + 1 prev = temp # 下一轮循环时，这个 temp 会成为新的“左上角” return dp[n]这段代码我第一次写的时候没加 temp 变量，结果跑出来的全是错的。给大家一个排查经验：只要结果比真实答案大，十有八九是把某个旧值弄丢了；如果结果比真实答案小，大概率是错误地复用了被新值覆盖的位置。这个观察在各类滚动数组题里都适用。
空间复杂度从 O(m * n) 降到 O(n)。严格来说，如果 m 和 n 相差很大，还可以先交换两个字符串，让 n 取较小的那个，进一步省空间。
3.3 工程上还有哪些变体值得了解
在实际业务里，我们有时不只想要“最少步数”，还想知道“具体做了哪些操作”。比如文件对比工具要标出哪几行被修改了。这时候光靠一个 int 数组不够，至少要加一个同尺寸的路径记录数组，记录每个格子是从哪个方向转移来的。最后从右下角反推回去，就能还原完整的操作序列。这个思路很多题通用，比如迷宫最短路径、最小代价路径都这么干。
另外，如果两个字符串特别长，比如上万字符的基因序列，O(m * n) 的时间可能扛不住。工程上会用分块算法或者近似算法，这是另一套话题了，但面试阶段能把 O(m * n) 的时空版本写清楚已经很扎实。
4. 踩坑实录：边界条件与细节问题排查
4.1 初始化与下标偏移，占这类题 80% 的错
我复盘了一下自己写编辑距离的报错记录，基本集中在几个地方。
第一个是 dp 数组维度。很多人习惯直接用 m 行 n 列的数组，然后强行在循环里处理边界，结果越写越乱。正确姿势就是 m+1 行、n+1 列，用“前 i 个字符”这种语义来对应空串。
第二个是初始化被跳过。有人写了首行首列的初始化，但在双层循环里把 i 从 0 或 j 从 0 开始跑，导致边界又被覆盖。循环必须从 1 开始，0 那行那列是地基，不要动。
第三个是下标偏移。s[i-1] 和 t[j-1] 是当前要比较的字符，s[i] 和 t[j] 是“还没处理到”的字符。这个偏移错一位，整个状态就全错了。
4.2 测试用例怎么设计才能“稳”
经验告诉我，字符串类 DP 题的测试用例一定要覆盖这几类：
- 两个空串，结果应该为 0；
- 一个空串一个非空串，结果应该等于非空串长度；
- 两个完全相同的字符串，结果应该为 0；
- 两个完全没有公共字符的字符串，比如 "abc" 和 "def"，结果应该是 3；
- 一个大字符串包含小字符串中的全部字符，比如 "horse" 和 "ros"。
这种“边界 + 极端 + 常规”的用例组合，对我来说是刷一切 DP 题的标配。
我记得有一次给一个学员讲这题，他写出来代码跑样例全过，交上去却超时。后来发现他在每一层循环里都调用了.append()来构建新列表，导致常数开销巨大。改成预分配列表之后，直接快了 20 倍。刷题时如果你不确定性能瓶颈在哪，先检查循环里有没有隐藏的 O(n) 操作，别急着怀疑算法复杂度。
5. 从编辑距离到整个 DP 题型的举一反三
5.1 和最长公共子序列的关系，一句话就通
编辑距离模型里，如果操作的代价不是 1，而是：插入删除代价为 1、替换代价为 2，那么这个问题就跟最长公共子序列（LCS）直接挂钩了。核心观察是：任何编辑操作都可以理解为“保留 LCS 中的字符不动，其余字符要么删、要么插”。所以当替换代价很高时，最优策略一定是尽可能多地保留公共部分。
LCS 的状态定义是 dp[i][j] 表示 s 前 i 个字符和 t 前 j 个字符的最长公共子序列长度，转移方程几乎和编辑距离同构：
- s[i-1] == t[j-1] 时，dp[i][j] = dp[i-1][j-1] + 1；
- 不相等时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
把这两个题放在一起对比着刷，效果比我单独刷十道题还好。因为它们共享同一副“骨架”，只是每个状态位上的聚合方式不同，一个是取 min，一个是取 max。
5.2 更多相似模型：区间 DP 与线性 DP 的识别
编辑距离、LCS 这类题目，特征是“两个序列互相匹配”，叫双序列 DP。还有一类常见的是单序列上的区间 DP，比如“最长回文子序列”。它的状态是 dp[i][j] 表示 s[i...j] 区间内的答案，转移时看 i 和 j 两个端点是否相等。如果不相等，取去掉左端点或去掉右端点两个子问题的较大值。
很多朋友分不清什么时候用线性 DP、什么时候用区间 DP。我的粗糙但好用的判断方法：如果状态转移只依赖“前一个位置”或“上一层”，那是线性 DP；如果转移需要同时考虑“左端点”和“右端点”，并且子问题是连续区间，那就是区间 DP。编辑距离虽然有两个维度，但它的依赖是线性的，属于双序列线性 DP。两者套路不同，但状态定义的思路一脉相承。
5.3 OP 表格：常见 DP 题型一眼识别
| 类型 | 常见信号词 | 状态设计习惯 | 典型例子 |
|---|---|---|---|
| 线性 DP | 序列、爬楼梯、打家劫舍 | dp[i] 表示前 i 个元素的结果 | 一维数组的递推 |
| 双序列 DP | 两个字符串、最小编辑距离 | dp[i][j] 表示两序列前缀匹配结果 | 编辑距离、LCS |
| 区间 DP | 回文子序列、戳气球 | dp[i][j] 表示区间 i 到 j 的结果 | 最长回文子序列 |
| 背包 DP | 容量、选或不选、最大价值 | dp[c] 表示容量为 c 时的最优值 | 0-1 背包、分割等和子集 |
| 树形 DP | 树状结构、依赖关系 | dp[node] 表示以该节点为根的子树结果 | 打家劫舍 III |
这张表不是让你背，而是提醒你：拿到题目先归类，再想状态，最后再写状态转移。顺序反了，代码写出来大概率是糊的。
6. 我刷完这道题后的复盘方法
最后再分享一点自己的想法。刷动态规划最忌讳的是“看完题解觉得懂了，关上屏幕又写不出来”。我自己总结了一个三遍刷题法，专门对付这种情况。
第一遍：拿到题目先自己想 15 分钟。想不出来就直接看题解，但只看状态定义和转移方程，不要看代码。然后合上题解，自己把代码写出来。第二遍：当天晚上，再重新做一遍这道题，要求自己不看任何参考资料，独立写完全部代码和测试用例。这一遍如果卡住，说明某些细节还没真正消化，需要立即回去翻。第三遍：一周之后再来一次，这时候重点不是写代码，而是尝试用口头把“为什么状态要这么定义、为什么转移方程是这三项取 min”讲清楚。能讲清楚，才算真的吃透了。
0226 这道题我大概刷了三遍，每一遍都有新发现。第一遍学会了标准解法，第二遍意识到滚动数组的临时变量容易坑人，第三遍才真正理解了它和 LCS 共用同一副骨架。这大概就是刷题最实在的乐趣：同一道题在不同阶段反复做，你会清晰地看到自己的成长轨迹。
如果你正在刷力扣的动态规划专题，正好也做到类似的编辑距离题目，我建议你别急着跳过，多花点时间把状态转移的“为什么”彻底想明白。这一题想通了，后面遇到双序列 DP 的变体，你会轻松很多。
