字符串之间的"改一下最短要几步"这类问题，看着不起眼，却是很多人动态规划之路上绕不过去的一道坎。信息学奥赛一本通里编号 1276 的这道题，标题就四个字——编辑距离，它讲的正是把一个字符串通过插入、删除、替换三种操作变成另一个字符串，求最少操作次数。第一次接触它的人通常会卡在状态怎么定、转移方程为什么长那样；而刷过几遍的人又会发现，下标从 0 还是从 1 开始、初始化怎么写，每个细节都能让你从样例通过直接掉到全错。这篇就把 1276 这道例题从头到尾拆开，讲清楚动态规划的设计动机、二维表的手工推演、代码逐行注释、以及我踩过的那些坑，无论你是刚学完背包的初学者，还是想把这道模板题讲给别人听的教练，都能从中找到可直接抄作业的部分。
1. 先搞清楚编辑距离到底在解决什么
1.1 从"打错字"说起，问题的直觉理解
你在搜索框里输入 "aple"，系统却问"你是不是想找 apple"，这背后的核心计算之一就是编辑距离。它的定义非常朴素：给定两个字符串 A 和 B，允许三种操作——在任意位置插入一个字符、删除任意一个字符、把任意一个字符替换成别的字符，每次操作算一步，问用最少的步数把 A 变成 B 需要多少步。题目 1276 里 A 和 B 的长度都小于 2000，最终只要求输出这个最小步数，是一个纯数值答案。
理解这个问题的关键，是意识到三种操作之间存在"等价"和"冗余"关系。插入一个字符和删除一个字符互为逆操作，替换一个字符有时可以拆成"删一个再插一个"，但那样要多花一步，所以替换是更"划算"的独立操作。举个小例子，A = "cat"，B = "cut"，只需把中间那个 a 替换成 u，一步搞定，编辑距离是 1；A = "cat"，B = "cats"，末尾插一个 s，也是一步。这些简单的例子看起来毫无难度，但一旦字符串变长、字符顺序错位，人脑就彻底算不动了，这正是需要算法的原因。
我特别喜欢拿"翻译"来类比：把 A 看成原文，B 看成译文，编辑距离衡量的是两者在字符层面有多"像"。像 "kitten" 变成 "sitting" 这类经典例子，标准答案是 3（k→s，e→i，末尾补 g），很多教材都拿它来引入，因为它既展示了替换、也展示了插入，操作类型齐全，短小又好记。
1.2 为什么贪心和暴力都行不通
有人第一反应是"从左往右扫一遍，不一样就改"，这就是典型的贪心思路。它对少数情况凑巧正确，但很快会崩。比如 A = "ab"，B = "ba"，从左扫：第 1 位 a 和 b 不同，改一次变成 "bb"，再改第二位变成 "ba"，两步。可实际上有更好的解法吗？想想看，替换两次就是 2；但如果你删掉开头的 a 变成 "b"，再在末尾插一个 a 变成 "ba"，那是 2 步；直接交换是不允许的。所以这里 2 是最优，贪心正好命中了。
但换一组：A = "abcd"，B = "acbd"。从左扫，第一位相同，第二位 b 和 c 不同，若顺手改成 c，后面就乱了，可能要更多步。实际上最优是删掉 b、在 c 后插一个 b，共 2 步，而贪心容易改成 3 步甚至更多。贪心的根本问题是：当前位置"改还是删还是插"会影响后面所有字符的对齐方式，局部最优不代表全局最优，必须把"子问题"层层保留下来比较，这天然就是动态规划的土壤。
暴力搜索更不可行。每一步状态都对应一棵分叉树，分支因子是常数级别，长度 2000 的情况搜索空间大到无法想象，指数级复杂度直接爆掉。所以这道题的正解只有一条：动态规划，而且是一个二维的、时间 O(n·m)、空间 O(n·m)（可优化到 O(m)）的经典模型。
1.3 编辑距离在真实世界里的用武之地
别以为这只是竞赛题，编辑距离是实打实被工业界广泛使用的算法。第一类是拼写纠错与输入法候选：搜索引擎、手机输入法在用户打错字时，会计算输入串和词典里每个词的编辑距离，把距离最小的若干词作为"你想找的是不是……"推给你。第二类是生物信息学里的 DNA/蛋白质序列比对，把碱基或氨基酸看成字符，编辑距离（及其带权变体）能衡量两条序列的相似程度，是很多比对工具的基础。第三类是版本控制与文本差异工具，比如各种 diff 工具要展示两段文本"改了哪几行",其行级比较的内核思想也和编辑距离一脉相承。第四类甚至出现在语音识别、抄袭检测等场景，本质都是"两串东西差多少"的量化。
弄明白这四类应用，你就会明白为什么这道例题被反复拿出来讲：它不只是让你 AC 一道题，而是让你掌握一个能迁移到无数真实问题里的建模套路。顺带说一句，很多人搜这道题会连带跳出"弗洛伊德算法"，那其实是另一个领域的东西——弗洛伊德用来求图上任意两点间最短路，是三重循环松弛；编辑距离是字符串对齐的动态规划。两者唯一相通的地方是都涉及"多阶段决策取最优"，但状态、转移、场景完全不同，别把它们的方程记混了。
2. 动态规划设计：状态定义与转移方程的来龙去脉
2.1 状态为什么必须是二维的
动态规划第一步永远是定义状态。这道题里，答案不是"整个 A 变成整个 B"一步能算出来的，而是由"前缀变前缀"的子问题叠加而来。原因很简单：字符串的匹配是从左往右对齐的，你处理到某个位置时，需要同时知道"A 已经用掉了前几个字符""B 已经匹配了前几个字符",这两个信息缺一不可。
于是定义 dp[i][j]：把 A 的前 i 个字符，变换成 B 的前 j 个字符所需的最少操作次数。注意这里是"前 i 个"，下标含义要牢牢记住，很多人后面出错就是因为把这里的 i、j 理解成了第 i 个字符的下标。为什么是二维而不是一维？因为子问题有两个自由度——A 用多少、B 用多少。一维状态没法同时记录两个进度，所以二维是最小的必要维度。最终答案自然就是 dp[n][m]，其中 n、m 分别是 A、B 的长度。
把状态想成一张表会更直观：行代表 A 的前缀长度，从 0 到 n；列代表 B 的前缀长度，从 0 到 m。dp[i][j] 就是这张表第 i 行第 j 列的那个格子。填表的过程，就是把每个格子用它的左、上、左上三个邻居推导出来，这也解释了为什么二维表能从左上角一路填到右下角。
2.2 三种操作在状态转移里各自对应哪一步
理解转移方程的最好办法，是逆向思考：要得到 dp[i][j]，考虑最后一步操作作用在哪儿。假设我们已经在凑"用 A 的前 i 个字符得到 B 的前 j 个字符"，看三种操作分别意味着什么。
- 删除：如果 A 的第 i 个字符是多余的，把它删掉，那么问题就退化成"用 A 的前 i-1 个字符变成 B 的前 j 个字符",代价是 dp[i-1][j] + 1。
- 插入：如果 B 的第 j 个字符在 A 里没有对应，我们在末尾"补"一个，等价于"用 A 的前 i 个字符先凑出 B 的前 j-1 个字符",再补上第 j 个，代价是 dp[i][j-1] + 1。
- 替换：把 A 的第 i 个字符直接改成 B 的第 j 个字符，那么两边各消耗一个字符，退化成"用 A 的前 i-1 个字符变成 B 的前 j-1 个字符"，代价是 dp[i-1][j-1] + 1。
这三种"最后一步"的假设覆盖了所有可能，取它们的最小值就是答案。这里有个容易忽略的点：当 A 的第 i 个字符和 B 的第 j 个字符本来就相等时，替换这一步不需要花费代价，甚至比"替换"更省——直接沿用 dp[i-1][j-1]，一个字符完美对齐，一步都不用花。
2.3 状态转移方程的完整形式与推导
把上面的三种情况合在一起，就得到了完整的状态转移方程：
当 A[i] == B[j]（下标从 1 开始计）时：
dp[i][j] = dp[i-1][j-1]当 A[i] != B[j] 时：
dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1我先解释为什么相等时不用考虑另外两种加操作。假设 A[i] == B[j]，如果还去尝试删除或插入，那至少要多花一步，而 dp[i-1][j-1] 这个选择能做到比它们都不差，所以直接取它即可，无需再取 min。这是一个可以证明的结论，省掉了不必要的比较。
再说说不相等时为什么是三个里取最小再加一。dp[i-1][j-1] 对应"替换"，dp[i][j-1] 对应"插入"，dp[i-1][j] 对应"删除"，三者各自代表一种把当前字符对齐掉的思路，谁最省就选谁。注意这个方程天然满足"最优子结构"：大的问题答案由小的子问题答案拼出来，而且子问题之间没有循环依赖，保证了按顺序填表就能得到正确结果。
2.4 边界条件：空串是最重要的起点
任何 DP 都要处理边界，这道题的边界就是"其中一个是空串"。dp[i][0] 表示把 A 的前 i 个字符变成空串，那只能一路删，需要 i 步，所以 dp[i][0] = i；同理 dp[0][j] 表示用空串凑出 B 的前 j 个字符，只能一路插，需要 j 步，所以 dp[0][j] = j。dp[0][0] = 0 是自然而然的。
这两个边界看似简单，但它决定了整张表的"地基"。很多初学者代码思路完全正确，却因为忘了初始化第一行或第一列，导致后面所有格子都算错，样例过不去。我在下面还会专门拿一节把初始化的坑讲透。这里先记住一句话：第一行是"从空串到 B 的各前缀"，第一列是"从 A 的各前缀到空串"，它们的值就是下标本身。理解了这句话，初始化就再也不会写错。
3. 完整代码实现与逐行拆解
3.1 二维 DP 标准写法与详细注释
先上最标准、最好理解的二维版本。它是我们的"基准版本"，调通它之后再做空间优化才稳妥。
#include <bits/stdc++.h> using namespace std; int main() { string a, b; cin >> a >> b; int n = a.size(), m = b.size(); // dp[i][j]：a 的前 i 个字符变成 b 的前 j 个字符的最少操作数 vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); // 边界：第一列，a 的前缀全部删掉变成空串 for (int i = 0; i <= n; i++) dp[i][0] = i; // 边界：第一行，空串逐个插入得到 b 的前缀 for (int j = 0; j <= m; j++) dp[0][j] = j; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i - 1] == b[j - 1]) { // 字符相同，直接对齐，不花代价 dp[i][j] = dp[i - 1][j - 1]; } else { // 替换、插入、删除三选一，再补上当前这一步 dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1; } } } cout << dp[n][m] << endl; return 0; }几个细节值得单独说明。第一，字符串用string存储，下标从 0 开始，而 dp 表从 1 开始计前缀长度，所以访问字符时统一写a[i-1]、b[j-1]，这个偏移量是坑点重灾区。第二，min({...})这种三参数写法是 C++11 以来的初始化列表版本，如果评测环境偏老，可以改成min(min(x, y), z)。第三，二维数组用vector动态分配，避免大数组爆栈，长度 2000 时表有 2001×2001 个格子，用int大约 16MB，一般题目内存限制下没问题，但如果两串都接近 2000 且内存卡得紧，就需要下面的滚动数组版本。
3.2 手工推演一遍样例，把表填出来
代码只是形式，真正的理解来自手推。拿一本通 1276 的样例来走一遍：A =sfdqxbw，B =gfdgw。先用边界把第一行第一列填好，然后逐格推进，得到下面这张完整的 dp 表（行对应 A 的前缀，列对应 B 的前缀）。
| dp | "" | g | f | d | g | w |
|---|---|---|---|---|---|---|
| "" | 0 | 1 | 2 | 3 | 4 | 5 |
| s | 1 | 1 | 2 | 3 | 4 | 5 |
| f | 2 | 2 | 1 | 2 | 3 | 4 |
| d | 3 | 3 | 2 | 1 | 2 | 3 |
| q | 4 | 4 | 3 | 2 | 2 | 3 |
| x | 5 | 5 | 4 | 3 | 3 | 3 |
| b | 6 | 6 | 5 | 4 | 4 | 4 |
| w | 7 | 7 | 6 | 5 | 5 | 4 |
右下角 dp[7][5] = 4，正好是样例输出。你可以挑一个格子手动验算，比如 dp[2][2]（A 的前两个字符 "sf" 变成 B 的前两个字符 "gf"）：s≠g，取 min(dp[1][1]=1, dp[2][1]=2, dp[1][2]=2) + 1 = 2，但真实情况是 "sf"→"gf" 只需把 s 改成 g，一步即可，为什么表里是 1？回头看看表，dp[2][2] 实际填的是 1。这里我要纠正一下刚才的口算：dp[1][1] 是 A 的 "s" 变 B 的 "g"，值确实是 1；所以 min 里 dp[1][1]=1 最小，加一得 2？不对，等等——字符 s 和 g 不相等时才加 1，可对于 dp[2][2]，比较的是 a[1]='f' 和 b[1]='f'，它们相等，所以直接取 dp[1][1]=1。看，这就是相等分支省掉加一的威力。
我们再验一个不等的情况，dp[3][4]（A 的前三个 "sfd" 变 B 的前四个 "gfdg"）：a[2]='d'，b[3]='g'，不相等，取 min(dp[2][3]=2, dp[3][3]=1, dp[2][4]=3) + 1 = 1 + 1 = 2，和表一致。这种手推三五个格子，比读十遍代码都管用，尤其能帮你直观感受"三个邻居谁最小"到底在选什么。
3.3 空间优化：把二维压成一维
当 n、m 都到 2000 甚至更大时，二维表虽然能过，但空间是 O(n·m)。观察转移方程：dp[i][j] 只依赖它左边、上面、左上三个格子，也就是说填第 i 行时只需要第 i-1 行的数据，更早的行完全没用了。这就具备了滚动数组压缩的条件，把空间从 O(n·m) 降到 O(m)。
#include <bits/stdc++.h> using namespace std; int main() { string a, b; cin >> a >> b; int n = a.size(), m = b.size(); // dp[j] 表示当前处理到 a 的前 i 个字符时，变成 b 前 j 个字符的最少操作数 vector<int> dp(m + 1); for (int j = 0; j <= m; j++) dp[j] = j; // 相当于第 0 行 for (int i = 1; i <= n; i++) { int prev = dp[0]; // 保存 dp[i-1][j-1]，即左上角 dp[0] = i; // 当前行的第 0 列：dp[i][0] = i for (int j = 1; j <= m; j++) { int tmp = dp[j]; // 更新前它还是上一行的值，即 dp[i-1][j] if (a[i - 1] == b[j - 1]) { dp[j] = prev; // 对应 dp[i-1][j-1] } else { dp[j] = min({prev, dp[j - 1], dp[j]}) + 1; } prev = tmp; // 为下一列保留左上角 } } cout << dp[m] << endl; return 0; }这段代码最容易绕晕的就是三个变量的时序关系，我用一句话帮你锁定：更新 dp[j] 之前，先把它存进 tmp；此时 dp[j-1] 已经是本行（第 i 行）的新值，dp[j] 还是上一行的旧值，而 prev 是上一行、上一列的值。三者正好对应状态转移需要的"左、上、左上"。其中prev = tmp放在本轮末尾，是为了让下一列 j+1 在使用"左上角"时，拿到的是本行前一列更新前的旧值——这个细节如果写反，答案会悄悄错掉，但样例有时候还能过，非常阴险。
提示：滚动数组我强烈建议先在二维版上调通、拿到正确答案，再做这一步优化，并用同一组数据对拍验证。直接上手一维版，一旦出错你很难判断是方程错还是变量时序错。
3.4 输入输出与字符串读入的注意点
题目给的是两行字符串，中间可能有空格吗？根据一字通的题意，A 和 B 是普通字符串，用cin >> a >> b就能读，它会自动以空白符分隔。但如果字符串本身可能包含空格（某些变体题会这样），就必须用getline。这时常见坑是：如果前面用cin读过数字，缓冲区里会残留一个换行符，getline会读到空串，得先用getchar()或cin.ignore()吃掉那个换行。这道原题不涉及这个，但你在做同类型题时要有这根弦。
输出只有一个整数，最简单的cout << dp[n][m]即可。有的题会要求如果无解输出 -1 之类，但编辑距离一定是有解的，最坏情况就是全删全插，所以不必担心边界外的分支。
4. 常见坑与调试实录
4.1 下标偏移：0 起步与 1 起步的拉锯战
这是我见过最多人栽的地方。dp 表用 1 表示"第一个字符"，而字符串下标用 0 表示"第一个字符"，两者差了一位。如果你在代码里写成了a[i] == b[j]而不是a[i-1] == b[j-1]，当 i 或 j 取到长度时就会越界，轻则答案错，重则程序崩溃。解决办法有二：一是老实用i-1、j-1，二是干脆在字符串前面补一个占位符，让两个下标都从 1 开始对齐，比如读入后执行a = " " + a; b = " " + b;，之后统一用a[i]、b[j]。补占位符这个技巧我用了很多年，能显著减少下标错误，代价是多了两个字符的内存，完全可以忽略。两种写法都行，关键是整段代码风格统一，别一半用一个规则、一半用另一个规则。
4.2 初始化漏写或写错的连锁反应
初始化的坑有两种典型形态。第一种是压根忘了初始化第一行第一列，此时 dp 数组里都是默认的 0，结果 dp[i][0] 应该等于 i 却成了 0，整张表全部偏低，答案也偏小。第二种是初始化写对了范围但写错了方向，比如把dp[i][0] = i写成了dp[0][i] = i，行列颠倒，在 n≠m 时错误会被放大。我的经验是：写初始化时先在纸上画一个小表，把边界的值一个个标出来，再对着代码逐行核对，尤其是 n 和 m 不相等的时候。如果你用vector且长度写成了n+1和m+1，记住行的上界是 n、列的上界是 m，别写反。
注意：
dp[i][0] = i这一行很容易在重构代码时被删掉。养成习惯——凡是二维 DP，先肉眼扫一遍第一行第一列有没有赋值，再点运行。
4.3 字符比较与 min 的书写陷阱
字符比较本身很简单，但有一个隐藏问题：题目里的字符可能是大小写混合，甚至是非 ASCII 的宽字符。原题 1276 都是普通可见字符，直接==比较没问题。但如果遇到 Unicode 字符串，string里一个字符可能占多个字节，逐个char比较会得到诡异结果，这时就需要按码点切分，属于进阶内容，本题不涉及。
另一个高频小错是 min 的参数个数。用min({a, b, c})需要包含<algorithm>，某些环境下还要注意编译标准；用嵌套min(min(a,b),c)则绝对安全。还有一种错误是忘记加 1，写成dp[i][j] = min(...)而漏掉+ 1，这种情况下答案会系统性偏小，样例可能凑巧还对，但一提交就挂。我调试这类问题的土办法是：挑一个不相等的格子，手工算出期望值，再打印程序里的实际值，一眼就能看出是漏加还是取错邻居。
4.4 与最长公共子序列的混淆
编辑距离和最长公共子序列（LCS）长得太像了，都是二维、都是前缀、都有左上角转移，很多人背着背着就串味。我把区别钉死在这里：LCS 求的是"最多能匹配多少个字符"，相等时dp[i][j] = dp[i-1][j-1] + 1，不相等时取左边和上面的大者且不加代价；编辑距离求的是"最少要改多少步"，相等时dp[i][j] = dp[i-1][j-1]，不相等时在三个方向里取最小加一。一个求最大、一个求最小，一个相等时加一、一个相等时直接沿用。实际上两者还有一层关系：在只允许插入和删除、不允许替换时，编辑距离等于n + m - 2 × LCS。把这条关系记住，既能帮你区分两个模型，也能在需要时互相验证结果。
4.5 调试速查表
把上面这些坑整理成一张速查表，考试或比赛时对着排查效率很高。
| 现象 | 可能原因 | 排查办法 |
|---|---|---|
| 答案偏小且正好差一个固定值 | 漏写+1或边界没初始化 | 手工算一个不等格子的期望值对比 |
| 程序越界崩溃 | 用了a[i]但 i 可等于 n | 改成a[i-1]或补占位符 |
| n≠m 时全错，n=m 时对 | 初始化行列写反 | 检查dp[i][0]和dp[0][j] |
| 样例过但提交错 | 滚动数组 prev 时序错 | 用二维版对拍小数据 |
| 答案忽大忽小无规律 | 混用了 LCS 的转移式 | 逐个核对相等/不等分支 |
5. 举一反三：从模板题到变形应用
5.1 带权编辑距离：当三种操作代价不同
一本通这道题默认插入、删除、替换的代价都是 1，但现实中它们并不等值。比如某些场景下删除很贵、替换相对便宜，于是就有了"带权编辑距离"：给三种操作各设一个代价 w_del、w_ins、w_sub，转移方程变成 dp[i][j] = min(dp[i-1][j] + w_del, dp[i][j-1] + w_ins, dp[i-1][j-1] + (相等 ? 0 : w_sub))。改法只有几处，但思路完全一致。理解了基础版本，带权版本就是顺手套公式。
更有意思的是，当替换代价大于"删除加插入"之和时，替换操作永远不会被选，模型就退化成纯插入删除的编辑距离，正好对应前面提到的 LCS 关系。这个现象说明编辑距离的三种操作并非彼此独立，它们之间存在"性价比"的权衡，设计转移方程时 min 就是在做这种权衡。
5.2 输出具体操作路径而不只是次数
原题只要次数，但很多实际需求要"怎么改"。做法是：在填表的同时记录每个格子的决策来源（是替换、插入还是删除），最后从 dp[n][m] 反向回溯到 dp[0][0]，把路径还原出来。回溯时遇到相等格子就一起往左上走，遇到不等就根据当时取的 min 来自哪个方向决定输出哪种操作，逆序输出即可。这个技巧在文本 diff、操作序列生成里非常有用，也常被拿来当进阶练习。
写回溯代码有个小坑：反推时要重新比较字符是否相等，而不是只看到达方向，因为"替换"这个方向在字符恰好相等时其实代表"不改动"，输出时应该跳过。我一开始就在这里多输出了一堆无意义的替换，改了好几遍才对。建议回溯时把 dp 表和字符串一起打印出来对照，非常直观。
5.3 和其他 DP 模板的横向对比
放到更大的坐标系里看，编辑距离属于"序列对齐类"动态规划，和 LCS、最长上升子序列、正则匹配、通配符匹配、最短公共超序列这几类共享同一套骨架：二维状态、前缀划分、左/上/左上转移。把这几个模型聚在一起练，你会发现它们的差别主要就三点——相等时加不加一、不等时取 max 还是 min、要不要额外加常数。抓住这三点，一整类题就打通了。
| 模型 | 相等时 | 不等时 | 目标 |
|---|---|---|---|
| 编辑距离 | 取左上 | 三方取 min 再 +1 | 最小操作数 |
| 最长公共子序列 | 左上 +1 | 左右取 max | 最长匹配长度 |
| 最短公共超序列 | 左上 +1 | 上下取 min 再 +1 | 最短合并长度 |
| 通配符匹配 | 视规则而定 | 上下左取并 | 能否匹配 |
我自己复习 DP 时，习惯把这些方程列成一张对照表贴在桌角，做题卡壳时扫一眼，往往立刻就能定位是哪个分支记错了。这种"把同类模型打包记忆"的方式，比一道一道孤立地刷要高效得多，尤其适合准备竞赛的同学在冲刺阶段快速回忆。
6. 我在这道题上踩过的那些坑
说点书本上不太会写的东西。我第一次AC这道题花的时间远超预期，原因不是不会方程，而是连续栽在下标的坑里。当时我图省事，直接写了a[i] == b[j]，小数据没事，一放大到临界长度就段错误，调试工具一挂我才发现 i 走到了 n。后来我养成了一个近乎强迫症的习惯：只要写二维 DP，先在草稿纸画个 3×3 的小表，把边界和第一个内格的值算出来，代码跑完先打印这张小表对照，对了再放大数据。这个动作多花两分钟，能省掉的调试时间往往是半小时起步。
第二个体会是关于对拍的。滚动数组优化那次，我写得挺顺，样例也过了，结果交上去只过了三成测试点。后来我写了个小脚本，随机生成几组长度不超过 8 的字符串，分别跑二维版和一维版，几百组一比就发现有两组对不上。定位到具体是 prev 更新时机错了——在某些 j 位置，它拿了本行的新值当左上角，导致个别格子偏小。对拍这种"暴力版 vs 优化版"的交叉验证，是我认为性价比最高的调试手段，强烈建议每个做 DP 优化的人都备一套。
最后分享一个记忆诀窍。状态转移的三个方向，我用一句话记："左上管改，上管删，左管插"。左上角 dp[i-1][j-1] 对应把当前这对字符替换掉，上面 dp[i-1][j] 对应删掉 A 的一个字符，左边 dp[i][j-1] 对应在 A 里插一个字符补齐 B。顺着这句话，不用死记方程也能在考场上现推出来。至于边界，还是那句老话——第一行是第一串空串往 B 里插，第一列是 A 往空串里删，值就是下标本身。把这两句口诀内化，这道 1276 以及它的一大票亲戚题，基本就稳了。
