P2758「编辑距离」

1. 题目

题目链接：P2758「编辑距离」 。

题目描述

设 $A$ 和 $B$ 是两个字符串。我们要用最少的字符操作次数，将字符串 $A$ 转换为字符串 $B$。这里所说的字符操作共有三种：

1. 删除一个字符；

2. 插入一个字符；

3. 将一个字符改为另一个字符；

！皆为小写字母！

输入格式

第一行为字符串 $A$；第二行为字符串 $B$；字符串 $A$ 和 $B$ 的长度均小于 $2000$。

输出格式

只有一个正整数，为最少字符操作次数。

输入输出样例

输入 #1

sfdqxbw
gfdgw

输出 #1

4

2. 题解

分析

易知编辑距离是对称的，即将字符串 $A$ 变成字符串 $B$ 和将字符串 $B$ 变成字符串 $A$ 所需的最小操作数是一样的，也就是字符串 $A$、$B$ 之间的编辑距离。然后直觉感觉就是一道简单的 dp 题：

• 假设 $f[i][j]$ 表示字符串 $A[0..i-1]$ 和 $B[0..j-1]$ 之间的编辑距离，则有如下转移方程：

1. 如果 $A[i] = B[j]$，则 $f[i][j] = f[i-1][j-1]$。
2. 如果 $A[i] \neq B[j]$，则 $f[i][j] = \min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1$。
3. 边界条件为：$f[0][0] = 0, f[i][0] = i, f[0][j] = j$。

代码

# include <bits/stdc++.h>
# define MAXLEN 2005
using namespace std;

char a[MAXLEN], b[MAXLEN];
int f[MAXLEN][MAXLEN];

int main()
{
    scanf("%s%s", a, b);
    int alen = strlen(a);
    int blen = strlen(b);
    f[0][0] = 0;
    for(int i = 1; i <= alen; ++i) {
        f[i][0] = i;
    }
    for(int j = 1; j <= blen; ++j) {
        f[0][j] = j;
    }
    for(int i = 1; i <= alen; ++i) {
        for(int j = 1; j <= blen; ++j) {
            if(a[i-1] == b[j-1]) {
                f[i][j] = f[i-1][j-1];
            } else {
                f[i][j] = min(f[i-1][j], min(f[i][j-1], f[i-1][j-1])) + 1;
            }
        }
    }
    int ans = f[alen][blen];
    printf("%d\n", ans);
    return 0;
}