字符串之间的改一下最短要几步这类问题看着不起眼却是很多人动态规划之路上绕不过去的一道坎。信息学奥赛一本通里编号 1276 的这道题标题就四个字——编辑距离它讲的正是把一个字符串通过插入、删除、替换三种操作变成另一个字符串求最少操作次数。第一次接触它的人通常会卡在状态怎么定、转移方程为什么长那样而刷过几遍的人又会发现下标从 0 还是从 1 开始、初始化怎么写每个细节都能让你从样例通过直接掉到全错。这篇就把 1276 这道例题从头到尾拆开讲清楚动态规划的设计动机、二维表的手工推演、代码逐行注释、以及我踩过的那些坑无论你是刚学完背包的初学者还是想把这道模板题讲给别人听的教练都能从中找到可直接抄作业的部分。1. 先搞清楚编辑距离到底在解决什么1.1 从打错字说起问题的直觉理解你在搜索框里输入 aple系统却问你是不是想找 apple这背后的核心计算之一就是编辑距离。它的定义非常朴素给定两个字符串 A 和 B允许三种操作——在任意位置插入一个字符、删除任意一个字符、把任意一个字符替换成别的字符每次操作算一步问用最少的步数把 A 变成 B 需要多少步。题目 1276 里 A 和 B 的长度都小于 2000最终只要求输出这个最小步数是一个纯数值答案。理解这个问题的关键是意识到三种操作之间存在等价和冗余关系。插入一个字符和删除一个字符互为逆操作替换一个字符有时可以拆成删一个再插一个但那样要多花一步所以替换是更划算的独立操作。举个小例子A catB cut只需把中间那个 a 替换成 u一步搞定编辑距离是 1A catB cats末尾插一个 s也是一步。这些简单的例子看起来毫无难度但一旦字符串变长、字符顺序错位人脑就彻底算不动了这正是需要算法的原因。我特别喜欢拿翻译来类比把 A 看成原文B 看成译文编辑距离衡量的是两者在字符层面有多像。像 kitten 变成 sitting 这类经典例子标准答案是 3k→se→i末尾补 g很多教材都拿它来引入因为它既展示了替换、也展示了插入操作类型齐全短小又好记。1.2 为什么贪心和暴力都行不通有人第一反应是从左往右扫一遍不一样就改这就是典型的贪心思路。它对少数情况凑巧正确但很快会崩。比如 A abB ba从左扫第 1 位 a 和 b 不同改一次变成 bb再改第二位变成 ba两步。可实际上有更好的解法吗想想看替换两次就是 2但如果你删掉开头的 a 变成 b再在末尾插一个 a 变成 ba那是 2 步直接交换是不允许的。所以这里 2 是最优贪心正好命中了。但换一组A abcdB 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 个字符的最少操作数 vectorvectorint dp(n 1, vectorint(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({...})这种三参数写法是 C11 以来的初始化列表版本如果评测环境偏老可以改成min(min(x, y), z)。第三二维数组用vector动态分配避免大数组爆栈长度 2000 时表有 2001×2001 个格子用int大约 16MB一般题目内存限制下没问题但如果两串都接近 2000 且内存卡得紧就需要下面的滚动数组版本。3.2 手工推演一遍样例把表填出来代码只是形式真正的理解来自手推。拿一本通 1276 的样例来走一遍A sfdqxbwB gfdgw。先用边界把第一行第一列填好然后逐格推进得到下面这张完整的 dp 表行对应 A 的前缀列对应 B 的前缀。dpgfdgw012345s112345f221234d332123q443223x554333b665444w776554右下角 dp[7][5] 4正好是样例输出。你可以挑一个格子手动验算比如 dp[2][2]A 的前两个字符 sf 变成 B 的前两个字符 gfs≠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 的前四个 gfdga[2]db[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 个字符的最少操作数 vectorint 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放在本轮末尾是为了让下一列 j1 在使用左上角时拿到的是本行前一列更新前的旧值——这个细节如果写反答案会悄悄错掉但样例有时候还能过非常阴险。提示滚动数组我强烈建议先在二维版上调通、拿到正确答案再做这一步优化并用同一组数据对拍验证。直接上手一维版一旦出错你很难判断是方程错还是变量时序错。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且长度写成了n1和m1记住行的上界是 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 时全错nm 时对初始化行列写反检查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 以及它的一大票亲戚题基本就稳了。