对于长度相同的两个字符串A，B,其距离定义为相应位置字符距离之和。2个非空格距离是它们的ASCII码之差的绝对值。空格与空格的距离为0，空格与其他字符的距离为一定值k。在一般情况下，字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中，有一对距离最小的扩展，该距离称为字符串A和B的扩展距离。对于给定的字符串A和B，编程计算其扩展距离。

设字符串A和B的字串A[1..i]和B[1..j]的扩展距离为val(i,j)，则val(i,j)具有最优子结构性质，递归式：
val(i,j)=min{val(i,j-1)+k,val(i,j-1)+k,val(i-1,j-1)+dist(a_i,b_j)}
算法:
int comp()
{
 int i,j,tmp,len1,len2;
 val[0][0]=0;len1=strlen(str1);len2=strlen(str2);
 for(i=0;i<=len1;i++)
  for(j=0;j<=len2;j++)
   if(i+j){
    val[i][j]=MAXINT
    if((i*j) && (tmp=val[i-1][j-1]+dist(str1[i-1],str2[j-1]))<val[i][j])
      val[i][j]=tmp;
    if(i && (tmp=val[i-1][j]+dist(str1[i-1],' '))<val[i][j])
      val[i][j]=tmp;
    if(j && (tmp=val[i][j-1]+dist(str2[j-1],' '))<val[i][j])
      val[i][j]=tmp;
                    }
return val[len1][len2];
 }

int main()
{
    readin();
    cout<<comp()<<endl;
    return 0;
 }
请问这个算法的思路是什么啊？我没看懂。

看不太明，举个例说明一下。

这个程序有明显错误。
算法就是求最小值。

[此贴子已经被作者于2017-12-4 19:38编辑过]