编辑距离问题的动态规划算法

Problem description
设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离，记为 d(A,B)。试设计一个有效算法，对任给的2 个字符串A和B，计算出它们的编辑距离d(A,B)。

Input
输入的第一行是字符串A，文件的第二行是字符串B。

Output
程序运行结束时，将编辑距离d(A,B)输出。

Sample Input
fxpimu
xwrs

Sample Output
5

请给出完整的代码

其实就是把一个复杂的最优解问题分解成一系列较为简单的最优解问题，再将较为简单的最优解问题一步步分解，直到能够一眼看出为止。
　　我们拿"sailn"和"failing"这两个字符串作例子。首先我们定义这样一个函数——edit(i, j)，它表示字符串1的长度为i的子串到字符串2的长度为j的子串的编辑距离。
　　首先我们作出初始化edit(0, j) = j（字符串1子串长度为0，字符串2子串有多少个字符，就作多少次增加操作；于是同理，edit(i, 0) = i。）
　　这里，我们要注意到对于操作（4），即交换相邻字符串的操作，我们要把某个字符通过这个操作到另一个位置上，我们最多只能执行一次操作，即只能移动到邻位上。原因是什么呢？这是因为，移动两次的话，就没有优势了，它的操作等于两次替换操作的操作数。大于2次的时候，移动操作会更差。所以，我们要进行操作（4），最多只发生一次操作。
　　我们可以得出这样一段动态规划公式：
　　如果i == 0 且 j == 0，edit(i, j) = 0
　　如果i == 0 且 j > 0，edit(i, j) = j
　　如果i > 0 且j == 0，edit(i, j) = i（2、3点之前已经陈述）
　　如果0 < i ≤ 1 且 0 < j ≤ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，这里当字符串1的第i个字符不等于字符串2的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。
　　如果i > 1且 j > 1时，这个时候可能出现操作（4），由之前的推导，我们只能交换一次，否则就没有意义。这个时候在比较最小值中可能加入edit(i-2, j-2) +1，什么时候加入呢？假设i-2长度的字符串1子串和j-2长度的字符串2子串已经得出最优解，这个时候如果s1[i-1] == s2[j] 并且s1[i] == s2[j-1]，这时就在比较值中加入edit(i-2, j-2) + 1（这个1是交换一次的操作）