g[i, j]=Min{g[i-1, j]+k, g[i, j-1]+k, g[i-1, j-1]+aibi } 0≤i≤La 0≤j≤Lb
其中，k为空格与字符之间的距离；
aibi为字符ai与字符bi的距离。
初始值：g[0, 0]=0 g[0, j]=j·k g[i, 0]=i·k

楼上所说题目题库已有。。。

现实意义：一个一个用字母填空，现在，第一个串填到i处，第二个串填到j处
三种情况：
1、此两空填s1[i]和“空”
2、此两空填“空”和s2[j]
3、此两空填s1[i]和s2[j]
类似题目：编辑距离（PID：题库暂无此题），最长公共子序列长度（PID：476），相似基因（PID：366）……