把一个词改成另一个，最少几步

给两个串 $A$ 和 $B$ ，你只能用三种操作改写 $A$ ：删掉其中一个字符、插入一个字符、把某个字符改成另一个。目标是把 $A$ 变成 $B$ ，用的操作次数最少——这个最小次数，就叫 $A$ 到 $B$ 的编辑距离（Levenshtein 距离）。

三种基本操作各一例：删（去一字）、插（补一字）、改（换一字）。每种都记 1 步。

先看个具体的：把 "horse" 改成 "ros"。一条可行路线是——把 h 改成 r（horse→rorse），删掉第一个 r 后面的 o… 手工凑很容易凑不出最短。其实最优是 3 步：h→r（改）、删 r、删 e，剩下 ros。再看 "sitting"→"kitten"，最优也是 3 步（s→k、i→e、删末尾 g）。

难点在哪？此刻该删、该插还是该改，取决于两个串后面还剩什么——是个牵一发动全身的全局问题，贪心按不住。那把所有操作序列枚举一遍？序列长度不固定、分叉又多，直接爆炸。和 LCS 一样，这类两个串逐位对齐的问题，正是二维 DP 的主场。

状态与转移：三选一取最小

定状态。设 $dp[i][j]$ 表示：把 $A$ 的前 $i$ 个字符改写成 $B$ 的前 $j$ 个字符，所需的最少操作数。把「逐位对齐」当作阶段，每一步只决断末尾这一位怎么处理。

dp[i][j] 只看三个邻格：上邻（删 A[i]）、左邻（插 B[j]）、左上邻（改 A[i]→B[j]，或字符相同则免费匹配），三条路取最小。

只盯住两个串的末尾字符 $A[i]$ 与 $B[j]$ ，把 $dp[i][j]$ 拆成三条来路：

删 $A[i]$ ：把 $A[i]$ 丢掉，问题缩成「 $A$ 前 $i-1$ 个对齐 $B$ 前 $j$ 个」，再计 1 步 → $dp[i-1][j]+1$ 。

插 $B[j]$ ：在 $A$ 末尾补一个 $B[j]$ 把 $B$ 这位对上，问题缩成「 $A$ 前 $i$ 个对齐 $B$ 前 $j-1$ 个」，计 1 步 → $dp[i][j-1]+1$ 。

改 / 匹配：让 $A[i]$ 与 $B[j]$ 正面相对，问题缩成「前 $i-1$ 对齐前 $j-1$ 」。若两字本就相同，白赚一步不花代价；否则改一次记 1 步 → $dp[i-1][j-1]+[A[i]\ne B[j]]$ 。

三条路取最小，就是转移方程：

dp[i][j]=\min\big(\,dp[i-1][j]+1,\ dp[i][j-1]+1,\ dp[i-1][j-1]+[A[i]\ne B[j]]\,\big)

这里 $[A[i]\ne B[j]]$ 是艾弗森括号：两字不同取 1、相同取 0。还差边界——一个串为空时怎么办？

dp[i][0]=i,\qquad dp[0][j]=j

$dp[i][0]=i$ ：把 $A$ 前 $i$ 个字符改成空串，只能一个个删，删 $i$ 次； $dp[0][j]=j$ ：从空串造出 $B$ 前 $j$ 个，只能一个个插，插 $j$ 次。答案在右下角 $dp[n][m]$ 。

本质

编辑距离把「无穷多条操作序列」压成一张 $(n{+}1)\times(m{+}1)$ 的表：每一格只问「末尾这位删、插、还是改/匹配」，三个已算好的邻格取最小。指数级的改写路径，被 $O(nm)$ 个格子装下——这正是两串对齐类 DP 的通用骨架。

跟着算一遍

用 $A=$ "horse"、 $B=$ "ros" 走几步（下标从 1 记），把方程「跑起来」：

0

铺边界。 首列

dp[i][0]=i

（"horse" 前缀全删空：0,1,2,3,4,5），首行

dp[0][j]=j

（从空串插出 "ros"：0,1,2,3）。这是整张表的地基。

1

左上角 $dp[1][1]$ （

A[1]{=}\text{h}

vs

B[1]{=}\text{r}

，不同）：删 =

dp[0][1]+1=2

；插 =

dp[1][0]+1=2

；改 =

dp[0][0]+1=1

。取最小 →

dp[1][1]=1

（把 h 改成 r）。

2

命中相同字符 $dp[2][2]$ （

A[2]{=}\text{o}

vs

B[2]{=}\text{o}

，相同）：匹配这条 =

dp[1][1]+0=1

，比删（

dp[1][2]+1=3

）、插（

dp[2][1]+1=3

）都小 →

dp[2][2]=1

。字符相同就白赚一格，不加代价。

3

右下角 $dp[5][3]$ （

A[5]{=}\text{e}

vs

B[3]{=}\text{s}

，不同）：删 =

dp[4][3]+1=3

最小（改 =

dp[4][2]+1=4

、插更大）→

dp[5][3]=3

。正是 "horse"→"ros" 的编辑距离 3，与手算吻合。

下面的演示会把整张表逐格填满，每格高亮上 / 左 / 左上三个来源并标出被选中的那条。改改两个串，看表实时重算。

看它一格一格填出来

∅

r

o

s

∅

h

o

r

s

e

0

1

2

3

1

·

2

·

3

·

4

·

5

·

当前计算依赖来源被选转移已确定

dp[i][0]=i,\quad dp[0][j]=j

边界：首列表示逐个删除，首行表示逐个插入。这是整张表的地基。

进度

已暂停，第 1 步，共 17 步，1 倍速

深化：从「恒 1」到带权对齐

上面每种操作都恒记 1 步。但「编辑距离」的骨架其实更通用——只要把每种操作的代价换成任意权重，同一套三向取最小就变成了最小代价的序列对齐。这在生物信息（DNA 比对）、拼写纠错里天天用。

普通版：删 / 插 / 改各记 1。带权版：删 / 插（一个字符对「空位」）记固定代价 k，改（两字符相对）记它们的差异度，如 ASCII 差 |A[i]−B[j]|。

把方程里的三个「 $+1$ 」换成各自的权重，转移形状一字不改：

dp[i][j]=\min\big(dp[i-1][j]+c_{del},\ dp[i][j-1]+c_{ins},\ dp[i-1][j-1]+c_{sub}(A[i],B[j])\big)

典型如洛谷 P1279「字串距离」：删 / 插一个字符视作它与「空位」配对，记固定代价 $k$ ；把 $A[i]$ 改成 $B[j]$ 的代价是两者 ASCII 差 $|A[i]-B[j]|$ （相同则差为 0，自然免费）。边界也随之变成 $dp[i][0]=i\cdot k$ 、 $dp[0][j]=j\cdot k$ 。普通编辑距离，不过是「删插改代价全取 1」的带权对齐特例。

换个视角：编辑距离 = 带权序列对齐

「删 / 插」= 某字符与空位配对，「改 / 匹配」= 两字符正面配对。于是求编辑距离，等价于给两个串找一套最省代价的逐位配对方案——把恒 1 的权重换成任意 $c_{del},c_{ins},c_{sub}$ ，方程原样通用。

不止要距离，还要「怎么改」：回溯操作序列

$dp[n][m]$ 只告诉你最少几步，可很多时候我们想知道具体是哪几步——先删哪个、再改哪个。办法是从右下角回溯：站在 $dp[i][j]$ ，看它当初的值是从哪个邻格转移来的，就往那格走，同时记下对应的操作，一路退回 $dp[0][0]$ ：

站在 (i, j)，回头看它是从哪来的：
  若 A[i] == B[j] 且 dp[i][j] == dp[i−1][j−1]   → 保留，走向 (i−1, j−1)
  否则若 dp[i][j] == dp[i−1][j−1] + 1           → 改 A[i]→B[j]，走 (i−1, j−1)
  否则若 dp[i][j] == dp[i−1][j] + 1             → 删 A[i]，走 (i−1, j)
  否则                                          → 插 B[j]，走 (i, j−1)
倒着走到 (0,0)，把记录翻转，就是把 A 对齐到 B 的操作序列

下面这个演示就把回溯逐步走给你看：上排是 $A$ 的字符、下排是 $B$ 的字符，中间的徽标标出每一位是保留 / 删 / 插 / 改。拖动步进条，看 $A$ 一步步被对齐成 $B$ ——真正花代价的步数，恰好等于上面主演示算出的编辑距离。

h

改→

r

o

保留

o

r

删

·

s

保留

s

e

删

·

保留（字符相同，+0）改（替换一字，+1）删（去掉 A 的字，+1）插（补上 B 的字，+1）

A 应用前 0 步后∅目标 B = ros

进度

已暂停，第 1 步，共 6 步，1 倍速

把 "horse" 变成 "ros" 的一条最优编辑序列共 5 步，其中 3 步是真正花代价的删 / 插 / 改——正好等于编辑距离 3；其余为不花钱的「保留」。逐步走一遍，看 A 如何被一次次操作对齐到 B。

回溯的两个坑

① 并列时要定一个固定优先级（这里：匹配 / 改 > 删 > 插），否则多条最优路径会让输出飘忽。② 回溯读的是转移来源而非单纯比大小——务必让判断顺序和当初填表时「谁被选中」的规则一致，否则会还原出一条并不合法的操作链。

例题

P2758编辑距离洛谷原生普及/提高-

题意

给两个字符串

A

、

B

，每次可对

A

删一个、插一个或改一个字符，求把

A

变成

B

的最少操作次数。

为什么选它

最纯净的 Levenshtein 裸模板：删 / 插 / 改三向转移一次讲透，边界

dp[i][0]=i,\ dp[0][j]=j

写熟。是把「两串对齐」这套二维 DP 骨架肌肉记忆下来的第一题，一行不多一行不少。

转移 · 复杂度

dp[i][j]=\min(dp[i-1][j]+1,\ dp[i][j-1]+1,\ dp[i-1][j-1]+[A_i\ne B_j])

；时间

O(nm)

。

参考代码（标准三向转移）

C++

在洛谷打开 P2758

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

char a[2005], b[2005];
int f[2005][2005];               // f[i][j]：a 前 i 个字符改成 b 前 j 个的最少操作

int main()
{
    cin >> (a + 1) >> (b + 1);   // 下标从 1 开始存
    int n = strlen(a + 1), m = strlen(b + 1);

    for (int i = 0; i <= n; i++) f[i][0] = i;   // 边界：全删空
    for (int j = 0; j <= m; j++) f[0][j] = j;   // 边界：从空串插出来

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            int sub = f[i - 1][j - 1] + (a[i] != b[j]); // 改/匹配：同字 +0，异字 +1
            int del = f[i - 1][j] + 1;                  // 删掉 a[i]
            int ins = f[i][j - 1] + 1;                  // 插入 b[j]
            f[i][j] = min(sub, min(del, ins));          // ★三向取最小
        }

    cout << f[n][m] << endl;
    return 0;
}
// TAG: 线性DP 编辑距离 Levenshtein 串对齐

P1279字串距离洛谷原生普及+/提高

题意

给两个串与一个空位代价

k

。把两串对齐（允许在任一串插入「空位」），一段对齐的代价 = 各位配对代价之和：两字符对齐记 ASCII 差

|A_i-B_j|

，字符对空位记

k

。求最小总代价。

换个视角（带权编辑距离）

这就是把恒 1 换成权重的编辑距离：「删 / 插」= 字符对空位、代价

k

；「改 / 匹配」= 两字符相对、代价

|A_i-B_j|

（同字差 0，天然免费）。转移形状与 P2758 完全相同，只换掉三个代价项和边界

dp[i][0]=i\cdot k

。

为什么选它

把「编辑距离 = 带权序列对齐」这句话落到代码：看清删 / 插的本质是「对空位」、改的本质是「按差异计费」，就能把裸模板一眼改造成带权版。是从模板迈向建模的关键一题。

参考代码（带权对齐）

C++

在洛谷打开 P1279

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

char a[2005], b[2005];
int f[2005][2005];               // f[i][j]：a 前 i 个对齐到 b 前 j 个的最小总代价
int k;                           // 空位（删/插）的固定代价

int main()
{
    cin >> k >> (a + 1) >> (b + 1);
    int n = strlen(a + 1), m = strlen(b + 1);

    for (int i = 0; i <= n; i++) f[i][0] = i * k;   // 前 i 个全对空位，各计 k
    for (int j = 0; j <= m; j++) f[0][j] = j * k;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            int sub = f[i - 1][j - 1] + abs(a[i] - b[j]); // 改：代价 = 两字符 ASCII 差
            int del = f[i - 1][j] + k;                    // 删 a[i]：a[i] 对空位
            int ins = f[i][j - 1] + k;                    // 插 b[j]：空位对 b[j]
            f[i][j] = min(sub, min(del, ins));
        }

    cout << f[n][m] << endl;
    return 0;
}
// TAG: 线性DP 带权编辑距离 字串距离 序列对齐

练习

P1032[NOIP2002 提高组] 字串变换串变换的搜索版：给定若干「子串→子串」的替换规则，求把 A 变成 B 的最少步数。规则不再是单字符删插改，用 BFS 逐层扩展状态（双向 BFS 更稳），是「编辑思想」从固定三操作推广到任意规则的延伸。在洛谷打开