test

根据动态规划里相关定理，如果I是从S到E的最优路径（S,E）上的一个点，那么(S,I)和(I,E)分别是从S到I和从I到E的最优路径。

我们采用递推的算法，由S算起，如果用坐标表示，则是如此顺序：
(0,0), (0,1), … (0,N)
(1,0), (1,1), … (1,N)
…
(M,0),(M,1), … (M,N)
其中M和N分别是A和B的长度。由上面一个图我们可以知道，到达某一个点(i,j)的可能直接跳转路径的起始点分别是
1. (0,j), (1,j), …, (i-1, j).
这种情况下，假设我们在计算从(k, j)跳到(i, j)的代价，分两种情况，一种情况是j和k去匹配，而k+1到i之间的点没有东西匹配，认为是Del；另一种是j和i匹配，而k到i-1之间的点没有东西匹配，认为是Del，所以累计代价取两种情况的最小者：
AccuD(i,j) = Min(AccuD(k,j) + D(Del from k+1 to i), AccuD(k,j) – D(k,j)+D(i,j)+D(Del from k to i-1)
2. (i,0), (i,1), …, (i,j-1)
这种情况与上面类似，只不过遍历列而不是行，并且把Del修改为Ins。
3．(i-1, j-1)
这种情况没有任何Ins或者Del
AccuD(i,j)=AccuD(i-1,j-1)+D(i,j)

取这三种情况下最小的AccuD作为点(i,j)的累积代价，并且记录下到达(i,j)的最短路径由哪个点跳转而来。

遍历完所有的点之后，我们就可以根据路径跳转记录由最后一个点(N,M)反推得到最优路径。