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

使用f[i][j] 表示：把a[1~i]与b[1~j]相匹配的有最小操作次数的操作方式

在最后a[i]和b[j]匹配时，我们可能会用到增加字符，减少字符，改变字符三种方案，故我们把集合划分为3类

第一类是最终需要我们进行增加字符，则情况必须是a[1~i]和b[1~j-1]已经相匹配上了，我们只需要对a字符串进行一次增加操作，故这里的状态表示为：f[i][j-1] + 1，也就是在f[i][j-1]匹配所需要的最小操作次数的基础上进行加1

第二类是最终需要我们进行减少字符，则情况必须是a[1~i-1]和b[1~j]已经相匹配上了，我们只需要对a字符串进行一次减少操作，故这里的状态表示为：f[i-1][j] + 1，也就是在f[i-1][j]匹配所需要的最小操作次数的基础上进行加1

第三类是最终需要我们进行改变字符，则情况必须是a[1~i-1]和b[1~j-1]已经相匹配上了，我们需要进行这个状态进行判断，如果a[i]和b[j]是相同的，那么我们只需要在f[i-1][j-1]的基础上加0，也就是不需要操作，如果a[i]和b[j]是相同的，那么我们只需要在f[i-1][j-1]的基础上加1，也就是f[i-1][j-1]+1,在f[i-1][j-1]相匹配的基础上进行加1

那么我们就得到了状态转移方程，也就是：
????????????????????????????????????????f[i][j] = max(f[i-1][j] + 1,f[i][j-1]+1,f[i-1][j-1],f[i-1][j-1]+1);

#include<iostream>
using namespace std;
const int N = 1000 + 10;

int n, m;
char a[N], b[N];
int f[N][N];	//f[i][j]表示把a[1~i]和b[1~j]匹配上需要的最小次数的操作方式

int main() {
	cin >> n >> a + 1;
	cin >> m >> b + 1;

	//进行初始化操作
	for (int i = 0; i <= m; i++)f[0][i] = i;//如果想把a[0]和b[i]匹配，那么就只需要i次增加操作
	for (int i = 0; i <= n; i++)f[i][0] = i;//如果想把a[i]和b[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]);//如果不需要改了，那么上一层基础上加0
			else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);		 //如果需要改，那么就上一层基础上加1
		}
	}

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

?