这道题以前觉得很麻烦，别说求出DP的递推公式，光是判断要加多少分就烦死了。
在看了克雷伯格的《算法设计》后，利用里面的定理6.16，
对于i>=1与j>=1，最小比对代价满足下面的递推式：
OPT（i,j)=min[a(xi,yi)+OPT(i-1,j-1),a(xi,'-')+OPT(i-1,j),a(yj,'-')+OPT(i,j-1)
此外，(i,j)在关于这个子问题的一个最优比对M中，当且仅当这个最小值是由上面的第一个值达到的。
代码如下：
Alignment(X,Y)
数组A[0,...m,0...n]
对每个i初始化A[i,0]=西格玛a(xi,'-')
对每个j初始化A[0,j]=西格玛a(yj,'-')
for i = 1,...n
 for j = 1,...m
调用定理6.16计算A[i,j]
return A[X,Y]
注意字符串的长度和数组的对应，有时候要-1
争取这两周做些算法题到200题。加油O(∩_∩)O