状态表示:
f[i][j]表示所有将a[i ~ 1] 变成 b[1 ~ j]的操作方式
添加操作:
添加a[i + 1]之后a[1 ~ i + 1] 与b[1 ~ j] 完全匹配, 这样添加的字符就是b的最后一个字符b[j],所以在添加之前a[1 ~ i]与 b[1 ~ j - 1]匹配, 添加的操作数为1,将a[1 ~ i]变为b[1 ~ j - 1]的方案数为
f[i][j - 1]
,所以状态转移方程为:f[i][j] = f[i][j - 1] + 1
删除操作:
删除a[i]后a[1 ~ i - 1]与b[1 ~ j]完全匹配,因此删除前,a[1 ~ i - 1] 与 b[1 ~ j]匹配
将a[1 ~ i - 1] 与 b[1 ~ j]匹配的操作次数为f[i - 1][j]
,删除这一操作数为1 因此状态转移方程:f[i][j] = f[i - 1][j] + 1
修改操作:
此情况下要分类讨论
若a[i] == b[j],那么就不用进行替换操作,因为替换后a[1 ~ i - 1] 和 b[1 ~j-1]完全匹配,所以替换前必须满足匹配,匹配的操作数为f[i - 1][j - 1],修改的操作数为0,状态转移方程为
f[i][j] = f[i - 1][j - 1]
同理,若a[i] != b[j] 则还要进行1次修改,状态转移方程:f[i][j] = f[i - 1][j - 1] + 1
综上:状态转移方程为:f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1, f[i - 1][j - 1] + 1 or 0)
#include <iostream>
using namespace std;
const int N = 1e3 + 7;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
scanf("%d%s", &n, a + 1);
scanf("%d%s", &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 <= n; j++) {
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1); //添加和删除
f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
}
}
printf("%d\n", f[n][m]);
return 0;
}