最短编辑距离

题目

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

1. 删除——将字符串$A$中的某个字符删除。

2. 插入——在字符串 $A$ 的某个位置插入某个字符。

3. 替换——将字符串 $A$ 中的某个字符替换为另一个字符。

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

// input:
10
AGTCTGACGC
11
AGTAAGTAGGC
// output:
4

题解

以$f[i][j]$表示在$a[]$中的前$i$个字母变成$b$中前$j$个字母的操作的集合。

对于可进行操作：

• **删除：**说明删前的$a[1,i-1]$和$b[1,j]$相同，即$f[i][j]=f[i-1][j]+1$.
• **插入：**说明加前的$a[1,i]$和$b[1,j-1]$相同，即$f[i][j]=f[i][j-1]+1$.
• **替换：**说明除了$a[i]$和$b[j]$都一样，即$f[i][j]=f[i-1][j-1]+1$.
• 不动：$f[i][j]=f[i-1][j-1]$.

最后仅需思考如何初始化：

• 对于初始长度为$0$的$a$，只能插入，$f[0][j]$.
• 而对于长度为$0$的$b$，只能删除，$f[i][0]$.

#include<iostream>
#include<cmath>
using namespace std;
int n, m, f[1005][1005];
char  a[10005], b[1005];int main()
{cin >> n >> a + 1;cin >> m >> b + 1;for(int i = 1; i <= n; i ++)f[i][0] = i;for(int j = 1; j <= m; j ++)f[0][j] = j;for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;f[i][j] = min(f[i - 1][j - 1] + (a[i] != b[j]), f[i][j]);}}cout << f[n][m] << endl;return 0;
}