文档介绍：五、字符串编辑距离给定一个源字符串和目标字符串,能够对源串进行如下操作:。简单描述一下解该题的思想,源字符串和目标字符串分别为str_a、str_b,二者的长度分别为la、lb,定义f[i,j]为子串str_a[0...i]和str_b[0...j]的最小编辑距离,简单分析可知求得的str_a[0...i]和str_b[0...j]的最小编辑距离有一下三种可能:(1)去掉str_a[0...i]的最后一个字符跟str_b[0...j]匹配,则f[i, j]的值等于f[i-1, j]+1;(2)去掉str_b[0...j]的最后一个字符跟str_a[0...i]匹配,则f[i, j]的值等于f[i, j-1]+1;(3)去掉str_a[0...i]和str_b[0...j]的最后一个字符,让二者匹配求得f[i-1, j-1],计算f[i, j]时要考虑当前字符是否相等,如果str_a[i]==str_b[j]说明该字符不用编辑,所以f[i, j]的值等于f[i-1, j-1],如果str_a[i]!=str_b[j]说明该字符需要编辑一次(任意修改str_a[i]或者str_b[j]即可),所以f[i, j]的值等于f[i-1, j-1]+1。因为题目要求的是最小的编辑距离,所以去上面上中情况中的最小值即可,因此可以得到递推公式:f[i, j] = Min ( f[i-1, j]+1,   f[i, j-1]+1,   f[i-1, j-1]+(str_a[i]==str_b[j] ? 0 : 1) )维基百科中的描述如下:1)递归方法(用到动态规划)由上述的递归公式可以有以下代码:[cpp] viewplaincopy1.//求两个字符串的编辑距离问题  2.//递归版本,备忘录C[i,j]表示strA[i]...strA[size_A-1]与strB[j]...strB[size_B-1]的编辑距离   editDistance_mem(char *strA,int size_A,char *strB,int size_B){   **C=new int*[size_A+1];  (int i=0;i<=size_A;i++){  [i]=new int[size_B+1]();  7.}  8.//初始化  (int i=0;i<=size_A;i++){  (int j=0;j<=size_B;j++)  [i][j]=INT_MAX;  12.}   res=EDM(C,strA,0,size_A-1,strB,0,size_B-1);  14.//free mem  (int i=0;i<=size_A;i++){   [] C[i];  17.}   [] C;   res;  20.}   EDM(int **C,char *strA,int i,int A_end,char *strB,int j,int B_end){  (C[i][j]<INT_MAX)//做备忘   C[i][j];  (i>A_end){  (j>B_end)  [i][j]=0;    [i][j]=B_end-j+1;  29.}else if(j>B_end){  (i>A_end)  [i][j]=0;    [i][j]=A_end-i+1;  34.}   if(strA[i]==strB[j])  [i][j]=EDM(C,strA,i+1,A_end,strB,j+1,B_end);  {   a=EDM(C,strA,i+1,A_end,strB,j+1,B_end);   b=EDM(C,strA,i,A_end,strB,j+1,B_end);   c=EDM(C,strA,i+1,A_end,strB,j,B_end);  [i][j]=min(a,b,c)+1;  42.}   C[i][j];  44.}  2)矩阵标记法递推方法(也可称为矩阵标记法),通过分析可知可以将f[i, j]的计算在一个二维矩阵中进行,上面的递推式实际上可以看做是矩阵单元的计算递推式,只要把矩阵填满了,f[la-1, lb-1]的值就是要求得最小编辑距离