算法看不懂,请大神解释一下
对于长度相同的两个字符串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;
}
请问这个算法的思路是什么啊?我没看懂。