这篇文章是尝试给像作者一样的算法爱好者（业余的委婉说法）解释一下编辑距离求解方法的思考过程，其实也是为了强迫自己真正的吃透编辑距离求解的方法论，以期能达到举一反三的效果。根据以上受众定位，我首先还是引入一段对编辑距离的解释，然后再从递归到递推（动态规划）讲讲对这个问题求解本身的正向思考过程，而不是拿到一个解法来说明它的正确性。
编辑距离的定义是用增删改三种操作将一个字符串演变为一个目标字符串所需的操作次数。比如将horse转化为ros，可以是如下步骤：
1）删除h变成orse； 2）删除o变成rse； 3）增加o变成rose； 4）删除e变成ros
也可以是如下步骤：
1）改h为r变成rorse； 2）删r变成rose； 3）删e变成ros
显然第二种策略要优于第一种，但是这种演变策略的排列组合随着源串a和目的串b的长度增长会几何级数的增长。我们需要用程序来求解。
这是一个典型的考动态规划的编程题，很多文章都会给出一个递推公式，但是这个递推公式为何正确，得到这个公式的思考过程是啥，为什么这么思考？回答了这几个问题才算理解了编辑距离的精髓，而且才能有举一反三的可能性。看了很多解释的文章，感觉都是从结果来理解和解释递推过程反证过程的有效性，隔靴搔痒，没有讲到这个公式是怎么得来的，怎么一下子就能得出这么精妙的计算方法，感觉就像现在解释机器学习模型的原理那样，训练出来一个有效的神经网络结构，然后再试图解释每一层是在干嘛，然而并不是一开始设计的时候就知道会是这样。但编辑距离这个算法是完全由人想出来的，必然是有设计者的心路历程可循。下面讲下我对这个问题的理解思路。
最容易想到的方法是递归，递归函数以目标字符串和源字符串为输入参数，代码如下：
def lev(a, b):
if len(a) == 0 or len(b) == 0:
return max(len(a),len(b))
if a[0] == b[0]:
return lev(a[1:],b[1:]) #首字符相等则跳过
ADD = lev(a,b[1:]) # add b[0]到a的开始, 问题转化为求a,b[1:]的编辑距离，因为头部相同的字符不增加编辑距离
DEL = lev(a[1:],b) # del a[0]
REP = lev(a[1:],b[1:]) # set a[0] = b[0], 问题转为求a[1:],b[1:]，原因同计算a的解释
return 1 + min(ADD,DEL,REP)
如果当前源字符串a和目标字符串b的首字符相同则直接去头部得到a’/b’再递归，如果a或b有一个是空字符串了，那么就停止迭代，并把剩下的那些字符个数直接算到编辑距离（a为空，要让a==b，需要把b的所有字符都“增加”到a，如果b为空，那么要“删除”掉a的所有字符）。
常规情况分三条路走，每条路径就是编辑距离定义的一种操作方法。每一种操作都会让输入字符串发生变化从而把问题转化为一个更小的子集：
- 增加：目标字符串减少一个字符；无论是加到头部还是加到尾部，加的都是目标字符串中的字符，相同的部分就不需要参与到后面的迭代了，毕竟我们要算的是最小操作数
- 删除：源字符串减少一个字符；这个不需要解释
- 替换：两个字符串都减少一个字符；同增加的道理一样，此时源字符串不仅不增加而且还可以减少一个
返回值就是编辑距离，我们需要在三条路中选择最短的距离，还要加上1，不能忘了当前这次操作已经发生。
递归方便思考，但是有大量重复计算，因为这种盲目的遍历常常殊途同归到相同的路径，并继续重复走一遍。从一般方法论上讲，我们要在走这三条路径的每一次迭代上都互相保持信息沟通，不断的借鉴彼此的已有经验。这就是为什么大航海以及全球化以来，人类科技水平以指数级速度提升，因为我们互通有无，大量减少了重复造轮子对人力物力的开销。扯的有点远，所谓借鉴已有经验，在逻辑上可以叫做“递推”，那么如何把上述递归转化为递推呢？
递归是遍历问题的可能处理方法，把原始问题层层分包，直到不可分割的最小原子问题，然后再顺着调用栈层层回溯，对比所有分支的结果来找到问题的解。
递推仍然是搜索，不过它是更高效的搜索，是动态有序的，每一轮的递推都是在前提条件完备的情况下做出的有效探索，是有规划的。每次不一定是最终路径上的探索，但绝对不是重复的无效探索。子问题的规模是逐渐扩大的，最终把问题扩展到原始输入，而每一次探索得到的都是当前子问题的解。实际上就是把递归的过程倒过来，把最原子的公共操作抽象出来统一计算一次（这些原子问题的求解往往是非常简单易懂的），然后从最原子问题结果出发，一步步的推导出最后结果，过程中每次子问题的扩大都直接借鉴上一层的结果。每一层都是渐进有序的扩大问题，不会重复计算。
针对编辑距离的问题，递推的终点就是问题扩大为a、b的编辑距离，而最后一次探索当然还是从三种操作中来选择（末尾字符相同直接可以不考虑，直接去掉也不影响问题的最终结果）：
- 增加：a.append(b[-1])
- 删除：a.pop()
- 替换：a[-1] = b[-1]
根据前面的递归算法，回溯到最顶层调用时，也就是我们的最后一步推理的前提条件是已知如下三个子问题结果：
lev(a, b[0:-1]); lev(a[0:-1],b);lev(a[0:-1],b[0:-1])
推理过程是：
- if a[-1]==b[-1]: lev(a,b) = lev(a[0:-1],b[0:-1])
- else: lev(a,b) = min(lev(a, b[0:-1])+1, lev(a[0:-1],b)+1, lev(a[0:-1],b[0:-1])+1)
在当前两个子串都非空时，推理过程是完备的，没有漏掉任何操作可能。具体的过程可以是先固定a，每次将b扩展一个字符，b扩展到原始问题字符串时，a扩展一个字符，每次扩展都考虑了三种定义的操作。虽然扩展本身看起来是增加操作，但是这里是子问题的扩展，并不是编辑字符串，而无论是a还是b扩展了一个字符后，都会带来整个问题的变化，不能只针对扩展出的这个字符考虑问题，要从这个新问题求解的角度来重新审视，而定义的三种操作都是针对一个字符的，所以也只需要借鉴上述三种子串组合（lev(a, b[0:-1]); lev(a[0:-1],b);lev(a[0:-1],b[0:-1])）。同时，每一步的问题扩大并不会影响推理的正确性，这个问题没有后效性，每次扩大a或b都只取决于前一次的状态，而与达到之前状态所走的路径无关。当子串a[0:i]、b[0:j]有一个为空时，另一个子串的字符数就是当前两个子串的编辑距离，因为不是全部删除就是全部增加，这就是最初的原子问题了。
根据这个公式，只要我们找到最小子问题，从他们开始，一步一步为后面更大的问题提供前提条件，就能求得问题的解，而且不会重复计算。这里的最小子问题就是把空转化为一个字符（空 => x），一个字符转换为空（x => 空），一个字符转化为另一个字符（x => y）等。比如先把空串编辑为空，x，xy，再到xyz；编辑距离分别为0,1,2,3，因为空串已经不能划分子串，这就已经是最小子问题了，而这个问题的求解则非常简单，不需要复杂的探索，因为从空到所有字符串，一个个的增加就是最简单的编辑方式。而这些子问题的结果就为下一步把x编辑为空，x，xy，xyz提供了递推条件。
总结为递推公式就是：
这里借助一张二维表格来推演出最后结果（有时需要三维甚至以上的数组存储中间状态）
表格（按二维数组存储，记作dp）的每一格填的数据dp[i][j]是对应坐标表示的两个子串a[0:j]和b[0:i]的编辑距离，计算方法很简单：
1）看下纵坐标i和横坐标j对应的两个字符a[j-1]和b[i-1]是否相同，如果相同转到第3步
2）计算ADD = dp[i][j-1]+1; DEL = dp[i-1][j]+1; REP = dp[i-1][j-1]+1，转到第4步
3）计算ADD = dp[i][j-1]+1; DEL = dp[i-1][j]+1; REP = dp[i-1][j-1]
4）dp[i][j] = min(ADD,DEL,REP) ，如果表格未填满，返回1）否则最后一个填入的值就是a和b的编辑距离
这个计算法是完全遵循上述递推公式的，只是为了便于理解和推算，用了表格形式记录结果；据此实现代码也非常简单：
def minDistance(self, word1, word2):
l1 = len(word1)
l2 = len(word2)
if l1 == 0 or l2 == 0:
return max(l1, l2)
stat = [ [0] * (l1+1) for i in xrange(l2+1) ]
# 直接给出所有原子问题的解
for i in xrange(l1+1):
stat[0][i] = i
for i in xrange(l2+1):
stat[i][0] = i
for i in range(1,l2+1):
for j in range(1,l1+1):
a = 0
if word1[j-1] == word2[i-1]:
a = stat[i-1][j-1]
else:
a = stat[i-1][j-1] + 1
# 每次扩展出的新问题都要把三种可能到达的操作考虑一遍
stat[i][j] = min(a,stat[i-1][j] + 1,stat[i][j-1] + 1)
return stat[l2][l1]
当然，上述算法还是有优化空间的，比如不需要一个完整的表格，只需要当前计算的那一行及其上一行就可以了，这样可以优化空间复杂度；还可以做一些预处理，把两个字符串相同的大段部分跳过，只针对剩下的不同部分来求解，这样对时间复杂度也有优化效果。
参考文献：https://en.wikipedia.org/wiki/Levenshtein_distance