跟LCS很像，根据LCS的思路考虑，

f[i][j]表示，a的前i个基因序列和b的前j个基因序列需要的最少操作数
则：
f[i][j] =  min
{
	若 a[i] == b[j] f[i][j] = f[i-1][j-1];
	若 不等：
	插入：f[i][j] = f[i][j-1] + 1;
	删除: f[i][j] = f[i-1][j] + 1;
	替换：f[i][j] = f[i-1][j-1] + 1;
}
注意初值：
f[0][0] = 0;
f[i][0] = i;
f[0][i] = i;

• Re:谁能给我说一下，这个思路是怎么想到的啊？怎么才能想到这个面~~？ 谢谢了！ (17) qazzxc135 2012-04-04 09:00:17