一本通 1276：【例9.20】编辑距离
看完题目后，整个人都懵了，这题咋整？
哎呀，知道知道，用动态规划做
不要慌，我们慢慢分析....
目录
做题前须知
状态转移
如果 a[i] == b[j]
如果 a[i] != b[j]
做删除操作
做插入操作
做替换操作
初始化
输出
最终代码
做题前须知
读完题发现要输出 让A字符串变为B字符串最少要几步
变化方式有3种 👇
- 删除一个字符
- 插入一个字符
- 改变一个字符
注意啦！
只能改变A字符串
只能改变A字符串
只能改变A字符串！！！！
重要的事说3遍😁
状态转移
这题 dp[i][j] 代表 让a[1~i]变为b[1~j]字符串最少要几步 相信这个大家肯定都知道
那如何状态转移？
如果 a[i] == b[j]
假设每个字符串后面都是x
A |-----------------------| x
B |-----------------------| x
像这样👆 那俩 x 就根本不用管，所以操作数就等于dp[i-1][j-1]
第一个转台转移方程闪亮登场👇
dp[i][j] = dp[i-1][j-1]
如果 a[i] != b[j]
假设一个字符串后面是x，一个字符串后面是y
做删除操作
A |--------------------------| x
B |-----------------------| y
我们是不是只要让a[1 ~ i-1] 和 b[1 ~ j] (淡蓝色部分) 相等然后再删除 ‘x' 就行了，所以...
dp[i][j] = dp[i-1][j] + 1
为啥还加个1啊，删掉那个 ’x' 不就是一步嘛？所以还要 +1
做插入操作
A |----------------------| x
B |-------------------------| y
我们是不是只要让a[1 ~ i] 和 b[1 ~ j-1] (淡蓝色部分) 相等然后再在A串结尾添加 'y' 就行了，所以...
dp[i][j] = dp[i][j-1] + 1
做替换操作
A |------------------------| x
B |------------------------| y
我们是不是只要让a[1 ~ i-1] 和 b[1 ~ j-1] (淡蓝色部分) 相等然后再将A串结尾的 'x' 替换成 'y' 就行了，所以...
dp[i][j] = dp[i-1][j-1] + 1
最后，只要将三个值算出来 再取个最小值 就可以赋值到dp[i][j]了
总结起来dp[i][j]的人生大概就是这样👇
/ a[i]==b[j] dp[i-1][j-1]
dp[i][j] ------ / dp[i-1][j] 删除
\ a[i]!=b[j] --min--| dp[i][j-1] 插入
\ dp[i-1][j-1] 替换
初始化
状态方程考虑完了，接下来我们来想一想怎么初始化
一个空串变为b[1~i]要i步，为什么，一直在结尾插入不就完了
同样让a[1~i]变为空串也要i步，那i步不就是一直删除吧
所以可以得到
dp[i][0] = i
dp[0][i] = i
输出
cout << dp[n][m];一痛分析下来，相信你已经会写了
还是不会的小伙伴跟我来！
最终代码
//【例9.20】编辑距离
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2005;
int dp[N][N];
char a[N], b[N];
int main() {
cin >> a + 1 >> b + 1;
int n = strlen(a + 1), m = strlen(b + 1);
for (int i = 0; i <= n; i ++)
dp[i][0] = i;
for (int i = 0; i <= m; i ++)
dp[0][i] = i;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
if (a[i] == b[j]) //结尾相同
dp[i][j] = dp[i - 1][j - 1];
else {
dp[i][j] = dp[i - 1][j] + 1; //删除
dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1); //插入
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1); //替换
//在 删除 插入 替换 中 选出最优解
}
}
}
cout << dp[n][m];
return 0;
}
/*
【输入样例】
sfdqxbw
gfdgw
【输出样例】
4
*/