题目描述
将 <字符串 A> 经过若干操作使其等于 <字符串 A>, 求其最小操作次数
三种操作:1.删除 2.插入 3.修改
f[i - 1][j] + 1
此时 a 的前 i - 1 个被转化为了 b 的前 j 个的样式
再新考虑 a 的第 i 个,由于已经相同,所以把第 i 个删掉,操作数加一
f[i][j - 1] + 1
此时已经使 a 的前 i 个变为 b 的前 j - 1
所以需要把 a 加入一个,操作数加一
f[i - 1][j - 1]
是在不考虑第 i 个和第 j 个的最小操作数
由于比前两种少考虑了一个,一定小于等于前两种的操作数
当 a 的第 i 个和 b 的第 j 个相等时,不需要操作(最小操作数量)
当不等时,需要修改 a 的第 i 个,操作数量加一(在三种情况中找最小值)
样例
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N][N], n, m;
char a[N], b[N];
int main()
{
scanf("%d%s", &n, a + 1);
scanf("%d%s", &m, b + 1);
//边界时次数都被判断好了,这道题可以不用
//memset(f, 0x3f, sizeof f);
for (int i = 0; i <= n; i ++) f[i][0] = i; // 删除 i 次
for (int i = 0; i <= m; i ++) f[0][i] = i; // 添加 i 次
//判断让 a 的前 i 个和 b 的前 j 个相等的最小编辑次数
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
f[i][j] = min(f[i][j - 1] + 1, f[i - 1][j] + 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;
}