1.概念

　　编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括：(1)将一个字符替换成另一个字符，(2)插入一个字符，(3)删除一个字符。

　　相似度，等于“编辑距离+1”的倒数。

2.分析

　　设有字符串a[0...n]，b[0...m]。

　　(1)当a[i]=b[j]时，说明这时候不需要编辑操作。编辑距离保持，即f(i,j)=f(i-1,j-1)

　　(2)当a[i]!=b[j]时，可以有三种编辑操作。

　　其中删除和插入操作，只对一个下标i或者j产生影响。如在下图中，当前匹配到(t1,t2)处，如果采用删除'g'，只改变t1的下标。

　　

 　　其中替换操作，会对2个下标都产生影响。如在下图中，当前匹配到(t1,t2)处，如果将'g'替换成'm'，则下次就需要执行(t1+1,t2+1)处。

     

 　　所以可以推导出下面就是递推公式。

　　

3.用递归求解代码

#include
     
      #include
      
       char *a="abcgh";char *b="aecdgh";int min(int t1,int t2,int t3)   ///求三个数的最小值{    int min;    min=t1
       
        enda)  ///i指示超过a[]的范围时    {        if(j>endb)            return 0;        else            return endb-j+1;    }    if(j>endb)  ///j指示超过b[]的范围时    {        if(i>enda)            return 0;        else            return enda-i+1;    }    if(*(a+i) == *(b+j))    ///如果两个相等，则直接求下一个位置        return calculate(i+1,enda,j+1,endb);    else    {        t1=calculate(i+1,enda,j,endb);  ///删除a[i]或在b中插入a[i]        t2=calculate(i,enda,j+1,endb);  ///删除b[j]或在a中插入b[j]        t3=calculate(i+1,enda,j+1,endb);    ///替换        return 1+min(t1,t2,t3);    }}int main(){    int dis=calculate(0,strlen(a)-1,0,strlen(b)-1);    printf("dis=%d",dis);    return 1;}
       
      
     

 4.用动态规划求解代码

 

#include
     
      #include
      
       #define MAX 1000int dp[MAX][MAX];   ///dp[i][j]表示当前a[0..i-1]与b[0..j-1]的编辑距离char *a="agbgd";char *b="ggd";int min(int t1,int t2,int t3)   ///求三个数的最小值{    int min;    min=t1
      
     

 类似有：