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

1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。
对任给的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。


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


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


Sample Input
sfdxbqw
gfdgw


Sample Output
4

看一下《编程之美》一书中叫做“计算字符串的相似度”的这篇文章

回复 2楼 卡卡小罗

百度找找看！~~

编辑距离，动态规划的经典题目。很多书上都有

编辑距离 编辑距离
 
Time Limit:JAVA/Others2000/1000MS  Memory Limit:JAVA/Others131072/65536KB
Total Submit:95 Accepted:19  
 
Description  
 
假设字符串的基本操作仅为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。  
我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。  
下面我们定义两个字符串的编辑距离：对于两个字符串a和b，通过上述的基本操作，我们可以把a变成b或b变成a，那么字符串a变成字符串b需要的最少基本字符操作步数称为字符串a和字符串b的编辑距离。  
例如：a="ABC",b="CBCD",则a与b的编辑距离为2。  
你的任务就是：编一个快速的程序来计算任意两个字符串的编辑距离。  
 
 
 
Input  
 
输入包含多组测试数据。每组测试数据一行，为字符串A和字符串B。  
字符串的长度不大于1024，且全为字母。
 
Output  
 
编辑距离。  
 
 
 
Sample Input  
 
 
ABC CBCD
Sample Output  
 
 
2

代码如下：
Memory:4268K  Time:390MS
Language:G++  Result:Accepted

 
Source  
 

#include<stdio.h>

#include<math.h>

#include<string.h>

int c[1026][1026]={0};
 
int min(int a,int b,int c)
{

 int i=a;

 if(i>b) i=b;

 if(i>c) i=c;

return i;

}
 
 
int main()
{
char a[1025],b[1025];

 int i,j,k=1,i1,j1,temp;

 for(i=1;i<=1000;i++)

{c[0][i]=k;c[i][0]=k++;}

    while(scanf("%s %s",a,b)!=EOF)
    {

     i1=strlen(a);

     j1=strlen(b);

      for(i=1;i<=i1;i++)

           for(j=1;j<=j1;j++)

           {

               temp=(a[i-1]==b[j-1]?0:1);

            c[i][j]=min(c[i-1][j-1]+temp,c[i-1][j]+1,c[i][j-1]+1);

            
            
            
            
           }

           printf("%d\n",c[i1][j1]);

    }

return 0;


}