信息学奥赛一本通 1276 这道题也就是经典的编辑距离是我见过的把动态规划状态定义和转移推导讲得最透彻的一道入门例题。它排在第 9 章动态规划的靠后位置不是没有道理的——前面那些数字三角形、最长上升子序列、背包问题更多是让你熟悉用数组存中间结果这件事而编辑距离第一次逼着你认真去想这个 dp 值到底代表了什么物理意义每一步操作是如何映射到状态转移上的。很多人第一次看到题目描述里的三种操作插入、删除、替换会觉得直观可真到写转移方程的时候又会卡住网上抄一份代码能过换一道变形题就立刻写不出来根子就在于表格没亲手填过、状态没有真正吃透。这篇就按我自己从写崩到写顺的过程把这题彻底拆一遍顺带把一维滚动数组优化和一堆容易翻车的细节讲清楚。如果你也是刷到 1276 卡了半天或者刚学完背包想找个新题型练手这篇应该能帮你把这题钉死在脑子里。1. 编辑距离到底在考什么以及我第一次写崩它的完整经过先把题目意思用大白话过一遍。给你两个字符串 A 和 B你只能对 A 做三种操作在任意位置插入一个字符、删除任意一个字符、把任意一个字符替换成别的字符。问最少经过多少次操作能把 A 变成 B。注意这里操作只作用在 A 上目标是把 A 改造成 B而不是双向的。这个单向的理解很关键后面推转移方程时会反复用到。我印象特别深第一次写这题的时候我脑子里的第一反应是贪心——逐个字符对比不相等就替换长度不一样就在末尾补或者删。这个思路看起来挺合理结果随手造了几个数据就挂了。比如 A 是 abcB 是 bc按贪心从左往右比第一个字符 a 和 b 不等我就想替换替换完发现后面又得处理折腾下来得到 2 次但正确答案是 1 次直接删掉开头的 a 就行。贪心的问题在于它在每个局部位置都做了看起来省事的决定却没考虑这个决定会怎样影响后面的对齐关系。编辑距离的本质是一个全局最优的字符对齐问题必须把前面所有位置的最优结果都存下来才能决定当前位置怎么处理这正是动态规划登场的信号。再往深说一层这道题真正训练的是建模能力你得先把两个字符串的匹配抽象成两个前缀的匹配再定义出一个二维状态。这个从具体问题到状态定义的跳跃是动态规划里最难也最值钱的一步。后面的转移方程、边界处理、空间优化其实都是机械劳动真正拉开差距的就是能不能定义出正确的 dp 数组。我做这题的时候逼着自己问了三个问题我到底在求哪个子问题的最优解这个子问题的规模用什么维度刻画大规模答案能不能由小规模答案拼出来三个问题答清楚了方程几乎自己就出来了。顺便提一句有些同学搜信息学奥赛一本通 1276的时候会顺带看到弗洛伊德算法这种热词挂在一起。这里得泼盆冷水弗洛伊德是求多源最短路的图论算法跟编辑距离压根不是一回事一个是 DP 套在字符串上一个是 DP 套在图的最短路径上思路内核相通都是枚举中间点/中间状态做松弛但题目类型完全不同。别被热词带跑偏1276 就是一道纯粹的字符串动态规划题踏踏实实从状态定义开始。2. 把两个字符串摊成一张表dp 数组到底长什么样2.1 dp[i][j] 的物理含义必须先说清楚动态规划最忌讳的就是知道有 dp[i][j] 这个格子但说不清它代表什么。这题的 dp[i][j] 我给我自己定了一条硬规矩来记把 A 的前 i 个字符变成 B 的前 j 个字符所需要的最少操作次数。注意前 i 个前 j 个这两个前缀前缀的措辞一个字都不能含糊。它既不是把 A 的第 i 个字符变成 B 的第 j 个字符也不是整个 A 变成整个 B 的前 j 个。只有当前缀理解才能让边界初始化第一行第一列自然成立也才能让最后的答案是 dp[n][m]n 是 A 的长度m 是 B 的长度。为什么不直接用完整字符串当状态因为状态必须能由小到大地递推。如果 dp 状态是整个 A 变成整个 B那子问题就没法缩小了。而用前缀做状态dp[i][j] 的子问题就变成了 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 这三个更小的前缀问题递推链条就搭起来了。这个用前缀/区间来刻画子问题规模的套路在 LCS最长公共子序列、最长公共子串、回文串这一整类题里是通用的学会一个就能迁移一大片。2.2 手工填一次表比读十遍题解都管用我强烈建议每个初学这题的人都拿 A kitten、B sitting 这种短字符串在一张纸上老老实实填一遍表。行代表 A 的前缀从空串到全长列代表 B 的前缀每个格子里填 dp 值。填完之后你会发现整张表呈现出一种非常规整的层层向左上方向传播的形态最小值总是从左上三个格子里挑出来的。举个更小的例子A catB dog我手把手填一下dpdog0123c1123a2223t3333你看最后 dp[3][3] 3正好是三个字符全替换的次数。再换成 A abcB bcdpbc012a112b212c321最终 dp[3][2] 1对应删掉开头那个 a跟前面贪心反例的正确答案完全一致。手工填的过程里你会真切感受到当两个字符相等时答案是直接从左上角免费对角线传下来的不相等时才需要从左边、上边、左上三个方向挑最小的再加一。这种对角免费传、其他加一挑最小的手感就是这题的全部核心填过三五组数据之后基本就刻进肌肉记忆了。我再补一句关于表格理解的经验这张表其实隐含着一种对齐的几何意义。从左下到右上的任意一条单调路径对应着一种把 A 和 B 对齐的方案路径上斜着走代表字符匹配或替换横着走代表插入 B 的字符竖着走代表删除 A 的字符。dp 要求的就是所有可行路径里代价最小的那条。有了这个视角你甚至能反推出为什么转移方程里的三个来源正好对应三种操作一点都不会觉得它是凭空冒出来的。3. 状态转移方程的三种来源一个一个掰开看3.1 删除操作对应 dp[i-1][j]先看删除。假设我们决定把 A 的第 i 个字符删掉那么删完之后A 的前 i 个字符就只剩前 i-1 个了而我们的目标仍然是匹配 B 的前 j 个字符。也就是说删掉 A[i] 之后问题退化成把 A 的前 i-1 个字符变成 B 的前 j 个字符这个子问题的答案就是 dp[i-1][j]再加上刚刚那一次删除操作代价是 dp[i-1][j] 1。这个映射关系要理解透删除操作让 A 的消耗进度前进了 i 那一维但 B 那一维不动因为我们这个字符直接扔掉了不跟 B 的任何字符对应。所以删除的来源是正上方的格子。3.2 插入操作对应 dp[i][j-1]再看插入。插入的本质是为了匹配 B 的某个字符我们在 A 里凭空塞一个新字符进去。假设 B 的第 j 个字符需要靠插入来匹配那么问题就退化成把 A 的前 i 个字符变成 B 的前 j-1 个字符也就是 dp[i][j-1]再补上这一次插入代价是 dp[i][j-1] 1。注意这里 A 那一维不动B 那一维前进了一格。因为插入是往 A 里加字符我们并没有消耗 A 原有的字符只是借了一个新字符去对应 B[j]。所以插入的来源是正左方的格子。很多人分不清删除和插入谁对应上、谁对应左我的记忆口诀是删是在源串动手所以源串那一维往前退往上走插是往源串里加东西去追目标串所以目标串那一维往前退往左走。3.3 替换操作对应 dp[i-1][j-1]最后是替换。如果 A[i] 和 B[j] 不相等我们可以把 A[i] 直接改成 B[j]这样它俩就匹配上了剩下的问题是把 A 的前 i-1 个变成 B 的前 j-1 个即 dp[i-1][j-1]加上这一次替换代价是 dp[i-1][j-1] 1。替换的来源是左上方的格子因为 A 和 B 各消耗了一个字符去互相配对。到这里三种操作和三个方向的对应关系就完整了上删、左插、左上替换。把它们摆在一起转移方程自然浮现当 A[i] B[j] 时dp[i][j] dp[i-1][j-1]字符本来就相等白送一个匹配不花代价当 A[i] ! B[j] 时dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 13.4 字符相等时为什么必须单独处理有同学会问字符相等时不也能套用 min 那套公式吗逻辑上不行。因为替换的前提是两个字符不一样我才需要改如果本来就相等替换就变成了无意义的多花一步。你如果强行用 min(...)1会把一个本来 0 代价的匹配算成至少 1结果就是答案偏大。所以相等时必须走 dp[i-1][j-1] 这条免费通道。这也解释了手工填表时那条对角线的重要性——它就是字符串里本来就匹配的位置在向答案传播。不过有个小坑要注意相等时你可以只取 dp[i-1][j-1]不能再在三个里挑最小。因为 dp[i-1][j] 和 dp[i][j-1] 至少比 dp[i-1][j-1] 大挑它们只会让结果更差。这条我踩过理论上相等时也写成 min 三个值的话其实 min 出来的就是 dp[i-1][j-1]因为它是三者中最小的结果照样对但这样做逻辑不清晰、还多算两次属于没必要的写法。我建议还是老老实实 if-else 分开写一眼就能看出意图。4. 边界初始化第一行和第一列不是随便填的很多人写 DP 时对付边界就是dp[0][j] jdp[i][0] i背下来但说不出为什么。这题如果不把边界的物理意义想清楚一遇到变形题比如带插入/删除不同代价的版本就彻底傻眼。dp[i][0] 表示把 A 的前 i 个字符变成空串。怎么变只能一个个全删掉所以代价恰好是 i。这就是 dp[i][0] i 的来源它对应的是表格第一列。同理 dp[0][j] 表示把空串变成 B 的前 j 个字符只能一个个全插入代价是 j对应表格第一行。而 dp[0][0] 表示空串变空串代价 0这是递推的起点。你看边界值不是硬凑的它就是极端情况下只剩一种操作可选的必然结果。明白了这一层你再去看那道著名的变体——插入代价是 1、删除代价是 2、替换代价是 3求最小代价边界就得改成 dp[i][0] i * 2删除dp[0][j] j * 1插入转移方程的加数也得相应替换成对应操作的花费。如果只会背模板这题就废了理解了物理意义改起来是顺手的事。初始化在代码里就是两行循环for (int i 1; i n; i) dp[i][0] i; for (int j 1; j m; j) dp[0][j] j;注意要从 0 开始把第 0 行、第 0 列都铺满dp[0][0] 保持 0 不用动。千万别漏漏了边界后面所有递推都是错的。5. 把二维数组压成一维滚动优化的完整推导5.1 为什么能压状态来源的局部性前面写了二维版本但如果你追求更漂亮的实现一维滚动数组是必须掌握的。能压的原因很简单算 dp[i][j] 只用到三个格子——dp[i-1][j]上、dp[i][j-1]左、dp[i-1][j-1]左上。也就是说算第 i 行时只有第 i-1 行和第 i 行自己的信息有用第 i-2 行及更早的数据全部可以丢掉。这种状态只依赖相邻上一层的结构就是滚动数组的适用条件和背包的一维优化是同一个思想。5.2 pre 变量到底在救谁的命压成一维后数组 dp[j] 在某一轮里代表的是什么这里有个必须厘清的时序问题。当我们按 i 从小到大、j 从小到大的顺序遍历时进入第 i 轮的那一刻dp[j] 里存的还是第 i-1 行算出来的老值而在本轮里dp[j-1] 已经被更新成了第 i 行的新值。于是算新的 dp[j] 时旧 dp[j]还没被覆盖就是 dp[i-1][j]对应上dp[j-1]刚更新过就是 dp[i][j-1]对应左唯独 dp[i-1][j-1]左上被 dp[j] 的旧值覆盖前就已经没了因为 dp[j-1] 现在是 i 行的值不再是 i-1 行的值所以左上角这个值必须额外用一个变量 pre 存起来。这就是 pre 存在的唯一理由——它专门替我们保管那个即将被覆盖的旧 dp[j]也就是左上角。每次循环结束前把 pre 更新成当前 dp[j] 的旧值在覆盖之前下一轮它就成了新的左上角。5.3 一维版本代码与正确性验证#include bits/stdc.h using namespace std; char a[2005], b[2005]; int dp[2005]; int main() { scanf(%s %s, a 1, b 1); int n strlen(a 1), m strlen(b 1); // 第 0 行空串变成 b 的前 j 个字符代价为 j for (int j 0; j m; j) dp[j] j; for (int i 1; i n; i) { int pre dp[0]; // 此刻 dp[0] 是 dp[i-1][0]即左上角 dp[0] i; // 新的一行第一列 dp[i][0] i for (int j 1; j m; j) { int tmp dp[j]; // 先存下 dp[i-1][j]等下要传给 pre if (a[i] b[j]) { dp[j] pre; // 来自左上不花代价 } else { dp[j] min(min(pre, dp[j]), dp[j - 1]) 1; // pre 左上(dp[i-1][j-1])dp[j] 上(dp[i-1][j])dp[j-1] 左(dp[i][j-1]) } pre tmp; // 把左上角更新为本轮的旧 dp[j] } } printf(%d\n, dp[m]); return 0; }这段代码最考验人的就是 pre 的赋值时机。你在更新 dp[j] 之前必须先把 dp[j] 的旧值暂存到 tmp因为一旦 dp[j] 被覆盖dp[i-1][j] 就再也找不回来了。而 pre 要在用完作为左上角之后才被更新为这一轮的 tmp。顺序错了结果必然错。我验证一维对不对的办法很土但很好用拿一组短字符串把二维和一维各跑一遍把中间每一步的数组都打印出来对比。只要逐轮对得上就说明逻辑没问题。别嫌麻烦滚动数组这种靠变量时序维持正确性的写法光看不打印心里是没底的。6. 我在提交这道题时反复踩过的几个坑6.1 下标从 0 还是从 1 开始混乱是万恶之源这题我前后因为下标问题挂过好几次。二维数组 dp 天然要有第 0 行第 0 列当边界所以字符串我习惯从下标 1 开始存读入a 1这样 a[1] 对应第一个字符A 的前 i 个字符就是 a[1..i]非常顺。一旦混用下标 0 开始的字符串转移方程里的 a[i] 和 b[j] 就得改成 a[i-1]、b[j-1]边界也要跟着调稍微不留意就写错。我的建议是全程统一下标从 1 开始读入时用scanf(%s, a1)或cin (a1)然后 strlen 也传 a1把这一套固定下来能省掉一大半 debug 时间。6.2 字符数组开多大别刚好卡在边界题目一般给的字符串长度上限不会太小常见是到一两千这种量级数组一定要预留够最好按给的极限再往上加一点点余量比如开 2005 或 2010。开小了会直接运行错误或者读到莫名其妙的数据这种错误还特别难查因为它不报编译错误只是结果偶尔不对或者段错误。我吃过开 1005 结果数据长度 1000 加末尾 \0 正好越界的亏现在一律往大了开。6.3 二维数组的空间慎重考虑要不要全开如果字符串长度到 2000 以上二维 int 数组 2005×2005 大概是 16MB 上下很多评测环境的栈空间和内存限制其实能扛住但如果长度到 5000 甚至更大二维就危险了内存会爆。这就是为什么我强烈建议把一维滚动数组版本也练熟——长度一大二维就是死路一维才活得下去。另外二维数组如果开成局部变量容易爆栈稳妥做法是开成全局变量全局变量在静态存储区不占栈。6.4 相等判断用字符还是用下标别搞反if (a[i] b[j])比的是字符本身不是下标。有时候走神会写成if (a[i] b[i])或者拿 i、j 去比这两个字符下标相等但内容完全可能不同逻辑就全错了。这种低级错误一旦混进去程序不会崩只是答案错排查起来反而费劲。写的时候多念一遍比的是字符内容是 a[i] 和 b[j]。7. 从编辑距离往外延伸这几类变形值得顺手练把这题吃透之后最有价值的事情是顺着它做延伸因为你会在延伸里发现原来状态设计可以这样变。第一个方向是加操作代价也就是前面提到的插入、删除、替换各给不同权重。这种题在真实场景里其实很常见比如拼写纠错时键盘上相邻字母的替换代价可能比插入一个字母更低因为打错的概率不一样。改法就是把转移方程里统一的那个 1 换成对应操作各自的权重边界也要同步改本质没变。第二个方向是把它和最长公共子序列LCS建立联系。其实编辑距离允许替换之后跟 LCS 是有微妙关系的dp_edit[n][m] 和 LCS 的长度之间可以互相推导在只考虑插入删除的情况下编辑距离 n m - 2 * LCS。这个联系能帮你用另一种视角理解编辑距离也能在你怀疑自己答案对不对的时候提供一个交叉验证的手段。我自己有时会在写完之后拿 LCS 版本算一遍两边对不上就说明有一边写错了。第三个方向是把两个字符串推广到字符串和通配符比如 B 里带问号或者星号问号能匹配任意单个字符星号能匹配任意长度。这就是另一道经典题了转移方程会多出分支但底层的前缀状态思想完全一致。你会发现无论是编辑距离、通配符匹配还是正则匹配骨子里都是同一类二维前缀 DP差别只在当前位置允许哪些操作。最后说一个我从这题里真正带走的东西动态规划的关键永远是把状态的物理含义想明白而不是把方程背下来。编辑距离之所以是个好例题就因为它把看到操作、联想到状态转移方向这件事演示得特别清楚——删对应上、插对应左、替换对应左上这三个映射一旦内化你后面遇到的绝大多数字符串 DP状态转移都能自己推出来根本不用去搜题解。我自己现在的习惯是遇到没见过的 DP 题先画一张表问自己每个格子代表什么、从哪些格子能走过来想不清楚就先不写代码。这个习惯就是当年在 1276 上反复摔跤摔出来的比任何一份现成代码都值钱。