前言
什么是编辑距离呢？
我们把“从字符串A到字符串B”的最少操作次数称作编辑距离。操作包含了：插入，删除，替换。比如字符串A = “abc”，字符串B = “abcd”，那么从A到B只需要增加一个字母“d”，所以编辑距离为1；同样的，从B到A只需要删除“d”，所以编辑距离也为1。
状态转移
将需要求解的问题，转移成子问题的过程，叫做状态转移。刻画状态转移的表达式称为状态转移方程式。
仍拿计算两个字符串的编辑距离为例。如果我们已知字符串A = “abc”，字符串B = “abc”，那么它们的编辑距离等于字符串“ab”与字符串“ab”的编辑距离。这是两个字符串最后一个字母相同时的处理方式，其他情况就得用其他方式。如已知 A = “abc” 与 B = “abcd”，求A和B之间的编辑距离。有以下方式做参考：
第一种方式，对字符串A插入操作，需要插入的值是B字符串的最后一个字母，所以问题变成了求“abcd”与“abcd”的编辑距离，现在最后一个字母相同，可以用之前得到的结论，继而问题成了求“abc”与“abc”的编辑距离。这样看来，其实是把最初的问题转移了：求“abc”与“abcd”编辑距离 = 求“abc”与“abc”的编辑距离 + 1。“+1”是因为我们对字符串A做了一个插入操作。
第二种方式，对字符串A删除操作。问题成了这样：求“abc”与“abcd”的编辑距离 = 求“ab”与“abcd”的编辑距离 + 1。
第三种方式，对字符串A替换操作。替换操作是比较隐晦的，不易看出来（对电脑而言），我们需要额外举例。现在字符串A = “abcd” 字符串B = “abce”，肉眼能够分辨，将字符串A最后一个字母“d”换成“e”，A就变成B了。可计算机没那么聪明，它需要一个字母一个字母的去比较。当同时去掉字符串A与字符串B的最后一个字母，如果剩下字符串相同，那么我们认为两个字符串之间的转换可以通过一个替换操作完成。
以上三种方式中，我们总是只保留结果最小的值。编辑距离的定义对此做了说明——需要最小操作数。每一次子问题中的最优解，保证了最终结果最优。
综上所述，得到状态转移方程式如下：
"""
strA strB 表示A B两个字符串
get_edit_distance(strA, strB) 表示计算strA、strB之间的编辑距离
"""
if strA[-1] == strB[-1]: # 当最后一个字母相同时
distance = get_edit_distance(strA[:-1], strB[:-1])
else: # 当最后一个字母不同时
distance = min( # 只保留最优解的结果
get_edit_distance(strA, strB[:-1]) + 1, # 插入操作
get_edit_distance(strA[:-1], strB) + 1, # 删除操作
get_edit_distance(strA[:-1], strB[:-1]) + 1, # 替换操作
)递归实现
有了上面的转移方程式，利用递归计算编辑距离就比较容易了（但它效率实在不高）：
def get_edit_distance(strA, str2):
if len(strB) == 0: # 考虑字符串B为空字符串时
return len(strA)
elif len(strA) == 0: # 考虑字符串A为空字符串时
return len(strB)
else:
if strA[-1] == strB[-1]:
return get_edit_distance(strA[:-1], strB[:-1])
else:
return min(
get_edit_distance(strA, strB[:-1]) + 1,
get_edit_distance(strA[:-1], strB) + 1,
get_edit_distance(strA[:-1], strB[:-1]) + 1
)迭代实现
迭代其实是递归的反向实现。使用递归时，我们要从字符串的最后一个字母入手，迭代则需要从第一个字母入手。我们可以绘制一张表格，用于描述两个字符串的编辑距离的变化。这里字符串A = “mouuse”，字符串B = “mouse”。表格如下：
根据上述表格，我们可以很轻易得出A到B过程的子问题中的编辑距离。比如“mou”与“mouse”的编辑距离是2，“mouu”与“m”的编辑距离是3。我们接下来编写的程序，其目的就是去完成这张表。
这里有一个点需要注意，因为需要考虑空字符串，所以我们绘制的表格的大小不是len(strA) * len(strB)，而是(len(strA)+1) * (len(strB)+1)。
另外，Python创建一个二维数组可以用一个“土办法”：
d = [[0]*(len(strB)+1) for __ in range(len(strA)+1)]下面是完整实现：
def get_edit_distance(strA, strB):
d = [[0]*(len(strB)+1) for __ in range(len(strA)+1)]
# 当 strB 为空字符串时
for i, __ in enumerate("a" + strA): # 'a' 为填充物，表示从 strA 为空字符串的时候开始
d[i][0] = i
# 当 strA 为空字符串时
for j, __ in enumerate("a" + strB): # 'a' 为填充物，表示从 strB 为空字符串的时候开始
d[0][j] = j
# 注意range的第一个参数是1，因为我们得从第二行第二列的位置开始填表
# 第一行与第一列已经在前面初始化了
for i in range(1, len(strA)+1):
for j in range(1, len(strB)+1):
if strA[i-1] == strB[j-1]: # 与递归不同，不是从最后一个字母开始比较
d[i][j] = d[i-1][j-1]
else:
# 在插入、删除、替换操作中保留最优解
d[i][j] = min(d[i][j-1]+1, d[i-1][j]+1, d[i-1][j-1]+1)
return d[-1][-1]代码优化
对上面代码继续分析。
当最后一个字母相同时，状态转移方式为d[i][j] = d[i-1][j-1]，在表格中可以看到位置关系如下：
当最后一个字母不相同时，状态转移方程式为d[i][j] = min(d[i][j-1]+1, d[i-1][j]+1, d[i-1][j-1]+1)，在表格中可以看到位置关系如下：
也就是说，计算两个字符串的编辑距离，其实只需要保留左、上相邻元素，以及左上角相邻元素。所以我们不需要二维数组，一个一维已经够用，这样可以降低空间复杂度。
这里我建议对两个输入字符串的长度做比较，选出最短，用来作为一维数组的长度，尽可能减少内存开销：
def get_edit_distance(strA, strB):
strMaxlen = strA if len(strA) >= len(strB) else strB
strMinlen = strA if strMaxlen != strA else strB
d = [0] * (len(strMinlen)+1)
# ...然后对这个一维数组初始化。此刻我们需要明白一维数组的意义，现在的一维数组表示：存放当较长字符串为空字符串时，较短字符串中每个子字符串的编辑距离。所以初始化如下：
def get_edit_distance(strA, strB):
# ...
for i, __ in enumerate("a"+strMinlen):
d[i] = i
# ...由于我们数组d现在是一维的，只能保留一个维度的数据，而且这个数组总是存放“旧数据”。比如当我们计算“mouu”与“mouse”的编辑距离时，数组d中存放的是“mou”与“mouse”的编辑距离。接下来是代码最核心部分，也就是如何保留需要的三个位置中的数据：
def get_edit_distance(strA, strB):
# ...
for i in range(1, len(strMaxlen)+1):
# 由于数组d中的数据总是`旧数据`，对于新一行的第二个元素，d[0]就是其左上角元素
leftTop = d[0]
# 由于总是从第二个元素开始，所以第一个元素需要自己填写
d[0] = i # `for i in range(1, len(strMaxlen)+1)`
# 等价于 `for i, __ in enumerate("a"+strMaxlen)`
for j in range(1, len(strMinlen)+1):
# 当前位置元素在被新数据替换前，是下个位置的左上角元素，因此用临时变量存储起来
temp = d[j]
if strMaxlen[i-1] == strMinlen[j-1]:
d[j] = leftTop
else:
d[j] = min(d[j-1]+1, d[j]+1, leftTop+1)
leftTop = temp
# ...这里我想对“当前位置元素在被新数据替换前，是下个位置的左上角元素”说明一下。当我们的数组d中存放的数据是“4 3 2 1 1 2”时，新一行的数据填写会从左到右开始，所以当我们更新索引为n的元素之前，该位置上的值就是上一行中索引为n时的值。
完整代码如下：
def get_edit_distance(strA, strB):
strMaxlen = strA if len(strA) >= len(strB) else strB
strMinlen = strA if strMaxlen != strA else strB
d = [0] * (len(strMinlen)+1) # 通过不断地刷新横排，达到空间优化地目的
for i, __ in enumerate("a"+strMinlen):
d[i] = i
for i in range(1, len(strMaxlen)+1):
leftTop = d[0] # 充当左上角角色：d[i-1][j-1]
d[0] = i # 每一行的最左值
for j in range(1, len(strMinlen)+1):
temp = d[j]
if strMaxlen[i-1] == strMinlen[j-1]:
d[j] = leftTop
else:
d[j] = min(d[j-1]+1, d[j]+1, leftTop+1)
leftTop = temp
return d[len(strMinlen)]动态规划
那么什么是动态规划呢？
答：在各种局部解中选出可能达到最优的局部解，放弃其他局部解。寻找最优解的过程就是动态规划。
上述计算两个字符串的编辑距离，就是在用动态规划思想。其核心是：状态转移方程式。当你能够找出合适的方程式时，动态规划的脉络随之清晰。
还不快抢沙发