题干信息:
编辑距离，又称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的编辑距离Sample Input
kitten sitting
Sample Output
3
题目如上
这个题首先想到的是暴力bfs,觉得给的那么大的内存应该没问题
结果暴力bfs会爆内存...
因为对于dp的理解不足,没有想到动态转移方程
这个题将样例的字符串拆开,横向为s2,纵向为s1
这个是最终的结果
详细来说,起始是这样的
首先这个表格是一个横向为s2长度,纵向为s1长度的表格
从A2来看,即s1是一个空字符串,他要到达s2字符串所需要的步骤分别为1,2,3,4,5,6,7
同理从B1来看,将s2视为一个空字符串,s1分别删掉其中元素到达s2为空字符串要经过的步骤也是0,1,2,3,4,5,6
然后我们从C3这个格开始找,要从到达s有三种情况:
1.将k替换成s,即B2格+1=2(他上一步就是什么都不做,于是就是(j-1)(i-1)即B2块)
2.从空串中插入一个字符s,即从B3+1=2(他要先删除k变成空串(A3-B3))然后再插入s(B3-C3))
3.从串中把k删除,即从C2+1=2(他先将空串插入了s,(A2-C2))然后(C2-C3)这样删除k就可以变成s)
从以上3步中,选取最少的步数,即将k替换掉s,这样C3格的数字填1
总结:1.删除步骤即是从dp[i-1][j]+1;
2.插入步骤即是从dp[i][j-1]+1;
3.替换步骤即是从dp[i-1][j-1]+1;
4.从1-3中选择步数最少的
AC代码如下
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<set>const int Max=100000;
using namespace std;
typedef long long ll;
string s1,s2;
int len1,len2;
int dp[1005][1005];
int main()
{ios::sync_with_stdio(false);cin>>s1>>s2;len1=s1.length();len2=s2.length();for(int i=0;i<=len1;i++){dp[i][0]=i;}for(int i=0;i<=len2;i++){dp[0][i]=i;}for(int i=1;i<=len1;i++){for(int j=1;j<=len2;j++){int cost=1;if(s1[i-1]==s2[j-1])cost=0;int del=dp[i-1][j]+1;int ins=dp[i][j-1]+1;int sub=dp[i-1][j-1]+cost;dp[i][j]=min(min(del,ins),sub);}}/*for(int i=0;i<=len1;i++){for(int j=0;j<=len2;j++){cout<<dp[i][j]<<" ";}cout<<endl;}*/cout<<dp[len1][len2]<<endl;return 0;
}