题解 P2758 【编辑距离】

**分析** 状态：f[i][j]记录ai与bj的最优编辑距离 结果：f[m][n]，其中m、n分别是a、b的串长 初值：b串空，要删a串长个字符；a串空，要插b串长个字符 转移方程：当a[i]=b[j]时，f[i][j]=f[i-1][j-1]，否则， f[i][j]=min(f[i-1][j-1]+1,f[i][j-1]+1,f[i-1][j]+1) 说明：f[i-1][j-1]+1：改a[i]为b[j]； f[i][j-1]+1：a[i]后插入b[j]； f[i-1][j]+1：删a[i]。 **by 一本通** ------------ 下面是代码 ``` #include<cstdio> #include<cstring> #include<cmath> using namespace std; char s1[2001],s2[2001]; int f[2001][2001]; int main() { int n,m; scanf("%s\n%s",s1,s2); n=strlen(s1); m=strlen(s2); for(int i=1;i<=n;i++)f[i][0]=i; //到i位置为止把字符串A的内容全部删除 for(int i=1;i<=m;i++)f[0][i]=i; //在开头给字符串A添上和B到i位置相同的字符 for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1]; else f[i][j]=fmin(fmin(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1; } } printf("%d",f[n][m]); return 0; } ``` 结束，希望能给大家精确的题解 求过