一个字符串可以插入、删除、改变到另一个字符串，求改变的最小步骤。和最长公共子序列类似，用二维数组opt[i][j]记录字符串a中的前i个字符到字符串b中的前j个字符匹配所需要的最小步数。假如已知AG到GT的最小步数，AGT到GT的最小步数，AG到GTT的最小步数，求AGT到GTT的最小步数，此时T= =T，这个值是AG到GT的最小步数，AGT到GT的最小步数加一(AGT到GT的最小步数等于AGTT到GTT的最小步数，加一是将T删除的一步)，AG到GTT的最小步数加一(AG到GTT的最小步数等于AGT到GTTT的最小步数，加一是在AGT上增加T的一步)。假如已知AG到GT的最小步数，AGA到GT的最小步数，AG到GTT的最小步数，求AGA到GTT的最小步数，此时A! =T，这个值是AG到GT的最小步数加一(A改变为T)，AGA到GT的最小步数加一(AGA到GT的最小步数等于AGAT到GTT的最小步数，加一是将T删除的一步)，AG到GTT的最小步数加一(AG到GTT的最小步数等于AGA到GTTA的最小步数，加一是在GTTA上删除A的一步)。所以状态转移方程：
初始化的时候和最长公共子序列不同，因为第0行，第0列表示null转化到字符串情况，结果是字符串的长度：

if(str1.charAt(i-1)==str2.charAt(j-1))

    array[i][j] = Math.min(Math.min(array[i-1][j-1], array[i-1][j]+1), array[i][j-1]+1);

else

    array[i][j] = Math.min(Math.min(array[i-1][j-1]+1, array[i-1][j]+1), array[i][j-1]+1);

 

for(int i=0;i<=m;i++){

    array[i][0] = i;

}   

for(int i=0;i<=n;i++){

    array[0][i] = i;

}
谁能解释一下：AGT到GT的最小步数等于AGTT到GTT的最小步数，加一是将T删除的一步)，AG到GTT的最小步数加一(AG到GTT的最小步数等于AGT到GTTT的最小步数，加一是在AGT上增加T的一步)万分感激！！

• Re:不太明白状态转移方程！！谁能解释一下？？？ (16) united 2009-11-13 10:22:55