编辑距离问题之动态规划解法
在leetcode上遇到一道很有意思的题目：编辑距离问题。这也是一道字符串处理类型的题目，并且是求最值，很容易想到用动态规划来解决这个问题。直接看题目
题目本身不难理解，但是细想还是存在很多有疑问的地方的。下面一步一步分析。
1. 确定问题状态和dp数组含义
对于这个问题来说，由于设计到两个字符串，根据经验我们先设dp数组为一个二维的数组，具体含义一会再分析。对于本题来说，由于变化量只有两个字符串，因此状态就是两个字符串的下标了。然后我们再来分析dp数组的具体含义。由于是求最小编辑距离，也就是让s1通过最短的操作步骤变成s2（等效于s2变成1），因此，dp数组可以这样定义：dp[i] [j]的含义为s1[i]变成s2[j]所需要的最小编辑步数。再将这个定义带入分析一下，可以推导出我们最后要的结果，因此dp数组就这样确定下来。
2. 明确选择
题目已经将我们可做的选择都列出来了：
- 插入
- 删除
- 替换
除了已经列出来的这三个操作，其实还有第四个操作：什么都不做。当s1[i]与s2[j]匹配的时候，当然是什么都不做直接跳过啦，这些就是本题的选择。看起来这一步已经完成了，但其实仔细想想，如何用状态转移来表示这几个选择呢？
3. 状态转移方程
完成了前面的分析，我们便可以开始写状态转移方程了。
我们先分析匹配的情况：
当s1[i]和s2[j]匹配时，我们的选择当然是什么都不做，此时dp[i] [j]就取决于前面的操作，即dp[i] [j] = dp[i-1] [j-1];这种情况很容易分析出来。接下来看不匹配的情况。
当s1[i]和s2[j]不匹配时，我们就要考虑选择题目提供的三种操作的哪一种操作。但是在当前dp数组定义下，每个选择要如何表示呢？
1.插入
当我们选择插入操作时，即在s1[i]处插入s2[j]，此时便相当于s2[j]被匹配掉（因为插入的字母一定是等于s2[j]的，而s1相当的长度增加1，即dp[i+1-1]，这是和替换操作的区别所在）此时的dp[i] [j]取决于dp[i] [j-1]。又因为执行了插入操作，故：
dp[i][j] = dp[i][j-1]+1
2.删除
当选择删除操作时，即s1[i]处删除掉一个字母，s2[j]未被匹配掉，仍保持不变，因此dp[i] [j]就取决于dp[i-1] [j]了，即：
dp[i][j] = dp[i-1][j]+1
3.替换
当我们选择替换操作时，其实和插入操作有点类似，此时s1[i]被替换为s2[j]，因此s1[i]于s2[j]便匹配了（这里又和直接匹配的情况类似），因此最终结果为：
dp[i][j] = dp[i-1][j-1]+1
到这里，我们只要择优选择就可以了。状态转移方程就全部写出来了，算法的核心代码就是把这一部分翻译成代码语言即可。
4. base case
一般来说找base case都是顺手就完成的工作，而本题不愧是hard problem，连base case都不是直接能看出来的了。我们带入一个实例分析：当s2遍历完成时，此时s1如果还没有遍历完成，便只能选择插入操作，这应该就是base case了。因此base case就是当两个字符串分别遍历完成时的情况。
代码实现
下面给出两种不同的代码实现：
- dp数组方式
def minDistance(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (m+1) for _ in range(n+1)]
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = j
for i in range(n+1):
for j in range(m+1):
if s2[i-1] == s1[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(
dp[i-1][j]+1, # 插入
dp[i][j-1]+1, # 删除
dp[i-1][j-1]+1 # 替换
)
return dp[n][m]- 备忘录递归方式
def minDistance(s1, s2):
memo = {}
def dp(i, j):
if i == -1:
return j+1
if j == -1:
return i +1
if (i, j) in memo:
return memo[(i, j)]
if s1[i] == s2[j]:
memo[(i, j)] = memo[(i-1, j-1)]
else:
memo[(i, j)] = min(
dp(i-1, j)+1,
dp(i, j-1)+1,
dp(i-1, j-1)+1
)
return memo[(i, j)]
return dp(len(s1), len(s2))小结
本题算是一道小有难度的动态规划问题了，同时也非常经典。我在做这道题的时候，在几个地方都有卡住。
首先是关于如何表示题目所给出的三种操作的，这一点确实不太好想到，其次就是关于base case的设置，也不容易想到（数组要设置为dp[m+1] [n+1], dp[0] [0]设为空）。主要原因还是缺乏经验，继续学习！
