一、问题描述：设A和B是两个字符串，需要用最少的字符操作将字符串A转换为字符串B。这些操作包括：（1）删除一个字符；（2）插入一个字符；（3）将一个字符修改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A和B的编辑距离，记为d(A,B)。设计有效算法，对任给的2个字符串A和B，计算它们的编辑距离。样例输入：fxpimu、xwrs样例输出：5二、问题分析：不用管他三种方法是怎么操作的。我们用d[i][j]表示A[1…i]和B[1…j]的编辑距离，则有：1、如果A[i]==B[j]，则d[i][j]=dp[i-1][j-1]；2、如果A[i]!=B[j],则有三种情况：（即上面的三种情况）（1）删除一个字符：dp[i][j]=dp[i-1][j]+1;(因为行是A，删除一个元素就是删除一行，然后编辑距离次数+1)（2）插入一个字符：dp[i][j]=dp[i][j-1]+1;(插入一个字符，因为要求dp[i][j]，如果增加了一行的话，dp[i+1][j]是还没有填的，解决方法就是把插入一行相当于B减少一列，同理，上面也可以这样理解)（3）将一个字符修改成另一个字符：dp[i][j]=dp[i-1][j-1]+1;(修改肯定是朝着使字符串相等的方向修改对吧，那么相等的话就是A[i]==B[j]的情况，不过编辑距离增加了一步)三、状态转移方程：
dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+1));
四、子问题：就是A中第一个元素开始对B的每个元素比较，看是否相等。然后看第二个，第三个。。。。。。（填表操作）五、代码：我这里是dp[i+1][j+1]，这是因为我的一种习惯而已，我习惯from0ton，这种循环。如果喜欢dp[i][j]这样的，循环就得from1ton。
#include<stdio.h>#definemin(x,y)(x)<(y)?(x):(y)charA[101]={'f','x','p','i','m','u'};charB[101]={'x','w','r','s'};intna=sizeof(A)/sizeof(A[0]);intnb=sizeof(B)/sizeof(B[0]);intdp[102][102];voidsolve(){for(inti=0;i<=na;i++)for(intj=0;j<=nb;j++){if(A[i]==B[j])dp[i+1][j+1]=dp[i][j];elsedp[i+1][j+1]=min(dp[i][j+1]+1,min(dp[i+1][j]+1,dp[i][j]+1));}printf("%d\n",dp[na][nb]);}intmain(){solve();return0;}
