编辑距离

【题目描述】

　　　　设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：

　　　　1、删除一个字符；

　　　　2、插入一个字符；

　　　　3、将一个字符改为另一个字符。

　　　　对任意的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。

【题目链接】

　　　　http://ybt.ssoier.cn:8088/problem_show.php?pid=1276

【算法】

　　　　确定状态，最优决策促使状态转移。

【代码】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int i,j,len1,len2;
 4 char s1[2010],s2[2010];
 5 int dp[2010][2010];
 6 int main()
 7 {
 8     scanf("%s%s",s1+1,s2+1);
 9     len1=strlen(s1+1),len2=strlen(s2+1);
10     for(i=1;i<=len1;i++) dp[i][0]=i;
11     for(i=1;i<=len2;i++) dp[0][i]=i;
12     for(i=1;i<=len1;i++)
13         for(j=1;j<=len2;j++)
14             if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1];
15             else dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
16      printf("%d
",dp[len1][len2]);
17      return 0;
18 }