最短编辑距离

算法1

(线性DP) $O(n^2)$

1.状态定义

f[i][j] : 所有将a[1 ~ i] 变成 b[1 ~ j]的操作方式的操作次数的最小值

2.状态计算：

如何分类： 分类方式一般考虑的是最后一步

a的前i个字母，b的前j个字母，共有三种操作；

1.删除：a[1 到 i - 1] == b[1 到 j] ，删除 a[i] ,即方程为 f[i-1][j] + 1;

2.增加：a[1 到 i] == b[1 到 j - 1], 增加使a[i] = b[j]; ,即方程为 f[i][j-1] + 1;

3.更改操作：

这里我们可以再划分为不用修改的情况和修改的情况

 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);

，其中 +1 表示最后一步的操作;

3.边界情况

我们需要考虑两种情况

1.只能做增加操作：a的前0个字母与b的前1~j的字母进行匹配时

2.只能做删除操作：a的前1~j个字母与b的前0个字母进行匹配时

	for(int i = 1; i <= m; i++) f[0][i] = i;  //增加操作
	for(int i = 1; i <= n; i++) f[i][0] = i;  //删除操作

C++ 代码

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

const int N = 1010;

int n,m;
char a[N],b[N];
int f[N][N];  //f[i][j] 表示n的前i个字母变成b的前j个字母的操作次数的最小值

int main() {
	scanf("%d%s",&n,a + 1);
	scanf("%d%s",&m,b + 1);

	//处理边界情况
	for(int i = 1; i <= m; i++) f[0][i] = i;  //增加操作
	for(int i = 1; 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);
		}
	}
	printf("%d",f[n][m]);
	return 0;

}