f[i,j]表示串a的前i个字符和串b的前j个字符所能匹配的最大分数
DP转移方程：
f[i,j]=max{
f[i-1,j-1]+m[a[i],b[j]],
f[i,j-1]+m['-',b[j]],
f[i-1,j]+m[a[i],'-']
}
其中，m[x,y]表示字符x和字符y匹配的分数

边界特例：
f[0,0]=0
f[i,0]=f[i-1,0]+m[a[k],'-']
f[0,j]=f[0,j-1]+m['-',b[k]]

答案即输出f[len(a),len(b)]

• Re:我的DP转移方程。AC~ (7) chhaya 2009-08-16 08:59:51