收藏
关注编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
例如将kitten一字转成sitting：
sitten （k->s）
sittin （e->i）
sitting （->g）
所以kitten和sitting的编辑距离是3。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
给出两个字符串a,b，求a和b的编辑距离。
Input
第1行：字符串a(a的长度 <= 1000)。 第2行：字符串b(b的长度 <= 1000)。
Output
输出a和b的编辑距离
Input示例
kitten sitting
Output示例
3
很显然当a和b都很小时，肉眼可以看出来答案，比如样例。
所以不妨考虑用自底向上记忆化搜索取最优解的方法，即dp.
设dp[i][j]表示长度为i的字符串a与长度为j的字符串b的编辑距离。
为啥这么设？
因为在自底向上的过程中，发生变化的量就是i和j。
AC代码：
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 char a[1015],b[1015]; 6 int dp[1015][1015]; 7 int main() 8 { 9 10 cin>>a>>b; 11 int n=strlen(a),m=strlen(b); 12 //边界条件 13 for(int i=0;i<1005;++i) 14 dp[i][0]=dp[0][i]=i; 15 for(int i=1;i<=n;++i) 16 for(int j=1;j<=m;++j) 17 { 18 if(a[i-1]==b[j-1]) 19 dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]+1),dp[i][j-1]+1); 20 else 21 dp[i][j]=min(min(dp[i-1][j-1]+1,dp[i-1][j]+1),dp[i][j-1]+1); 22 } 23 cout<<dp[n][m]<<endl; 24 return 0; 25 }