动态规划 编辑距离¶
前置知识¶
最长公共子序列
目标¶
掌握例题代码
edit distance编辑距离¶
aka, Levenshtein distance莱文斯坦距离(aka, also known as)
举例
字符串A("xyzab")和字符串B("axyzc")，问至少经过多少步操作可以把A变成B。
我们还是从两个字符串的最后一个字符来考察即'b'和'c'。显然二者不相同，那么我们有以下三种处理办法：
(1)增加：在A末尾增加一个'c'，那么A变成了"xyzabc"，B仍然是"axyzc"，由于此时末尾字符相同了，
那么就变成了比较"xyzab"和"axyz"的距离，即d(xyzab,axyzc) = d(xyzab,axyz) + 1
可以写成d(i,j) = d(i,j-1) + 1。表示下次比较的字符串B的长度减少了1，而加1表示当前进行了一次字符的操作
(2)删除：删除A末尾的字符'b'，考察A剩下的部分与B的距离。即d(xyzab,axyzc) = d(xyza,axyzc) + 1
可以写成d(i,j) = d(i-1,j) + 1。表示下次比较的字符串A的长度减少了1
(3)替换：把A末尾的字符替换成'c'，这样就与B的末尾字符一样了，那么接下来就要考察出了末尾'c'部分的字符，
即d(xyzab,axyzc) = d(xyza,axyz) + 1
写成d(i,j) = d(i-1,j-1) + 1表示字符串A和B的长度均减少了1
例题，1276：【例9.20】编辑距离¶
// 示例代码
// 编辑距离的问题，和LCS很像很像
// 放在一块进行对比学习，更有帮助
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
char a[N], b[N];
int n, m;
int dp[N][N];
int main()
{
scanf("%s%s", a + 1, b + 1);
n = strlen(a + 1), m = strlen(b + 1);
// 初始化
dp[0][0] = 0;
for (int i = 1; i <= n; i++) dp[i][0] = i;
for (int j = 1; j <= m; j++) dp[0][j] = j;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
if (a[i] == b[j]) dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
}
cout << dp[n][m] << '\n';
return 0;
}