题目描述

给定两个长度分别为 $m,n$ 的字符串 $A$ 和 $B$，现在要将 $A$ 经过若干操作变为 $B$，可进行的操作有：

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

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

样例

输入样例1：

10 
AGTCTGACGC
11 
AGTAAGTAGGC

输出样例1：

4

基本思路

仍然是闫氏 dp 分析法。

状态表示

定义 $f_{i,j}$ 表示将 $A$ 中前 $i$ 个字符修改为 $b$ 中前 $j$ 个字符的最短编辑距离。属性是 $\min$.

状态计算

可以将 $f_{i,j}$ 分为四种情况讨论：

1. 删除操作：删除 $A_i$ 后，$A$ 中前 $(i-1)$ 个字符与 $B$ 中前 $j$ 个字符相等，所以此时 $f_{i,j}=f_{i-1,j}+1$.
2. 插入操作：在 $A_i$ 后插入一个字符，使得 $A$ 中前 $(i+1)$ 个字符与 $B$ 中前 $j$ 个字符相等，可以看做 $A$ 中前 $i$ 个字符与 $B$ 中前 $(j-1)$ 个字符相等，所以此时 $f_{i,j}=f_{i,j-1}+1$.
3. 修改操作：将 $A_i$ 修改为 $B_j$，使得 $A$ 中前 $i$ 个字符与 $B$ 中前 $j$ 个字符相等，可以看做 $A$ 中前 $(i-1)$ 个字符与 $B$ 中前 $(j-1)$ 个字符相等，所以此时 $f_{i,j}=f_{i-1,j-1}+1$.
4. 不操作：此时 $A_i=B_j$，即 $f_{i,j}=f_{i-1,j-1}$.

所以当 $A_i=B_j$ 时，$f_{i,j}=\min(f_{i-1,j}+1,f_{i,j-1}+1,f_{i-1,j-1})$; 当 $A_i\neq B_j$ 时，$f_{i,j}=\min(f_{i-1,j}+1,f_{i,j-1}+1,f_{i-1,j-1}+1)$.

与其他 dp 问题有一点不同，这里的 $f$ 数组需要初始化。对于所有的 $f_{0,i}$（$0\leq i\leq n$），其表示的是 $A$ 中前 $0$ 个字符变为 $B$ 中前 $i$ 个字符的最小操作数量，显然每一次都是插入操作，所以 $f_{0,i}=i$. 对于所有的 $f_{i,0}$（$0\leq i\leq m$），其表示的是$A$ 中前 $i$ 个字符变为 $B$ 中前 $0$ 个字符的最小操作数量，显然每一次都是删除操作，所以 $f_{i,0}=i$.

完整代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N][N];
char a[N], b[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) { //dp
            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];

    return 0;
}