试题编号：1119

ZYC编辑距离F920

难度级别：B； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B

试题描述

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

1、删除一个字符；

2、插入一个字符；

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

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

输入

第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于2000。

输出

只有一个正整数，为最少字符操作次数。

输入示例

sfdqxbw

gfdgw

输出示例

4

今天又考试了QAQ。

思路：这道题是一道典型的动规，输入字符串a和b后，我们知道有三种待转移情况：替换（dp[i][j]=dp[i-1][j-1+1)，删除（dp[i][j]=dp[i-1][j]+1），插入（dp[i][j]=dp[i][j-1]），当然这是不等的情况，如果相等就是dp[i][j]=dp[i-1][j-1]。既然我们要求最小，如果相等，就直接赋值就好了。如果不等，就用min判断这三种待转移状态哪个最小就好了。蛮简单的一道dp，只要想出转移方程的话这道题就很简单了。然后上参考代码：

1 #include
     
       2 using namespace std; 3 char a[2005],b[2005]; 4 int la,lb,dp[2005][2005]; 5 int main() 6 { 7     gets(a+1);//从1开始读入  8     gets(b+1); 9     la=strlen(a+1);//看字符串长度 10     lb=strlen(b+1);11     for(int i=1;i<=la;i++) dp[i][0]=i;//赋边界值 12     for(int i=1;i<=lb;i++) dp[0][i]=i;13     for(int i=1;i<=la;i++)14     {15         for(int j=1;j<=lb;j++)16         {17             if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1];//如果相等，就直接复制 18             else dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;//不等就判断哪种待转移状态最小 19         }20     }21     printf("%d",dp[la][lb]);//输出 22     return 0;//完美结束 23 }