这是个动态规划的问题：
分治思路
用分治的思想解决比较简单，将复杂的问题分解成相似的子问题。
假设字符串 a, 共 m 位，从a[1]到a[m]
字符串 b, 共 n 位，从b[1]到b[n]
d[i][j]表示字符串a[1]-a[i]转换为b[1]-b[j]的编辑距离。
那么有如下递归规律（a[i]和b[j]分别是当前要计算编辑距离的子字符串 a 和 b 的最后一位）：
当a[i]等于b[j]时，d[i][j] = d[i-1][j-1], 比如 fxy -> fay 的编辑距离等于 fx -> fa 的编辑距离
当a[i]不等于b[j]时，d[i][j]等于如下 3 项的最小值：
d[i-1][j]+ 1（删除a[i]（删除等价于插入操作，相当于插入b中插入a[i[）），比如 fxy -> fab 的编辑距离 = fx -> fab 的编辑距离 + 1
d[i][j-1]+ 1（删除 b[j]或者插入b[j])，比如 fxy -> fab 的编辑距离 = fxyb -> fab 的编辑距离 + 1= fxy -> fa 的编辑距离 + 1
d[i-1][j-1]+ 1（将a[i]b[j]同时删除（等价于交换操作）），比如 fxy -> fab 的编辑距离 = fxb -> fab 的编辑距离 + 1 = fx -> fa 的编辑距离 + 1
递归边界：
a[i][0] = i, b 字符串为空，表示将a[1]-a[i]全部删除，所以编辑距离为 i
a[0][j] = j, a 字符串为空，表示 a 插入b[1]-b[j]，所以编辑距离为 j
http://blog.csdn.net/pipisorry/article/details/46383947
像以上解决思路，是从后往前算的，比如我想知道edit_distance(a, b, i, j)我可能需要知道edit_distance(a, b, i-1, j-1)。
如果从前往后算，先算出各个子问题，然后根据子问题，计算出原问题，对于这个问题性能不错。
例如以字符串 a = "fxy", b = "fab" 为例：
首先建立一个矩阵，用来存放子问题及原问题的编辑距离，并将递归边界在矩阵中填好，如下：
然后计算 i = 1, j = 1 所对应的编辑距离：比较a[i]和b[j]是否相等然后根据递归规律算出这个值
比如在这种情况下a[i] = f和b[j] = f, 那么d[i][j]就等于d[i-1][j-1]等于 0
然后计算 i = 1, j = 2 直到算出 i = 3, j = 3, 原问题的编辑距离就等于d[3][3]
即要计算d[i][j]只需要知道3个位置上的值。
现在的时间复杂度已到了可接受范围，为 O(mn)。
