给定两个字符串S和T，对于T我们允许三种操作：
(1) 在任意位置添加任意字符 (2) 删除存在的任意字符 (3) 修改任意字符 问最少操作多少次可以把字符串T变成S？ 输入 第1行：字符串a(a的长度 <= 1000)。 第2行：字符串b(b的长度 <= 1000)。 输出 输出a和b的编辑距离 输入示例 kitten sitting 输出示例 3<span style="font-size:18px;">#include<cstdio> #include<cstring> char a[1100],b[1100]; int dp[1100][1100]; int min(int c,int d) { if(c>d) return d; return c; } int same(int i,int j) { if(a[i]==b[j]) return 0; return 1; } int main() { scanf("%s%s",a,b); int i,lena=strlen(a),lenb=strlen(b); for(i=0;i<=lenb;++i) dp[0][i]=i; for(i=0;i<=lena;++i) dp[i][0]=i; dp[0][0]=0; for(i=1;i<=lena;++i) { for(int j=1;j<=lenb;++j) { dp[i][j]=min(min(dp[i-1][j-1]+same(i-1,j-1),dp[i-1][j]+1),dp[i][j-1]+1); }//大家会不会对这个dp[i-1][j-1]+same(i-1,j-1)有点疑问，为什么不是 same(i,j) //因为字符串是从0开始的 } printf("%d\n",dp[lena][lenb]); return 0; }</span>
