python/TangDou/AcWing/LineDP/902.md

##AcWing 902. 最短编辑距离

一、题目描述

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：

1. 删除–将字符串 A 中的某个字符删除。
2. 插入–在字符串 A 的某个位置插入某个字符。
3. 替换–将字符串 A 中的某个字符替换为另一个字符。

现在请你求出，将 A 变为 B 至少需要进行多少次操作。

输入格式 第一行包含整数 n，表示字符串 A 的长度。

第二行包含一个长度为 n 的字符串 A。

第三行包含整数 m，表示字符串 B 的长度。

第四行包含一个长度为 m 的字符串 B。

字符串中均只包含大小写字母。

输出格式 输出一个整数，表示最少操作次数。

数据范围 1≤n,m≤1000

输入样例：

10 
AGTCTGACGC
11 
AGTAAGTAGGC

输出样例：

4

二、解题思路

与LCS（最长公共子序列）问题的状态表示是很接近的。

状态表示

f[i,j]：a[1..i]变成b[1..j]的操作步数。

现在要求的是：两个字符串的最短编辑距离，由于我们不知道最短编辑距离是多少，就希望知道 当前状态是从哪些状态转移过来，前面的状态可以通过 增加、删除、修改转移过来 。

属性

操作数的最小值，min。

状态计算

按题意划分为删除，增加，修改,相等四种情况

• 删除：把a[i]删掉之后a[1\sim i]和b[1\sim j]匹配.所以没删除之前，就有a[1 \sim i-1]与b[1 \sim j]匹配

\large f[i][j]=f[i-1][j] + 1

• 插入：插入之后a[i]与b[j]完全匹配，所以插入的就是b[j],那填之前a[1\sim i]和b[1\sim (j-1)]匹配

\large f[i][j]=f[i][j-1] + 1

• 替换：把a[i]改成b[j]之后想要a[1\sim i]与b[1\sim j]匹配,那么修改这一位之前，a[1\sim (i-1)]应该与b[1\sim (j-1)]匹配

\large f[i][j]=f[i-1][j-1] + 1

• 相等：如果本来a[i]与b[j]这一位上就相等，那么不用改，即

\large f[i][j]=f[i-1][j-1]

结论

f[i][j]   =   min(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+(a[i]  ==  b[j]?0:1))

初始化

细节问题：初始化怎么搞

先考虑有哪些初始化嘛

• f[0][i]:如果a初始长度就是0，那么只能用插入操作让它变成b

• f[i][0]:如果b的长度是0，那么a只能用删除操作让它变成b

• f[i][j] = INF 其它初始化为INF

二、实现代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];

// 最短编辑距离
int main() {
    cin >> n >> a + 1 >> m >> b + 1;

    // 初始化
    for (int i = 0; i <= m; i++) f[0][i] = i;
    for (int i = 0; i <= n; i++) f[i][0] = i;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            // 增加和删除
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            // 修改
            if (a[i] == b[j])
                f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else // 相等
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }

    cout << f[n][m] << endl;
    return 0;
}