问题：
题目来源：力扣（LeetCode）
leetcode72.编辑距离
难度：困难
分析： 经典的动态规划题。 一个小技巧，在DP表的第一行和第一列添加辅助行和辅助列，这样就免去了初始化时的麻烦。本题可以从辅助行和辅助列得到需要的base case，所以可以使用这个技巧。
解决方法： 1：二维DP
递推公式： if word1[i - 1] == word2[j -1]：dp[i][j] = dp[i][j] = dp[i - 1][j - 1]， if word1[i - 1] != word2[j -1]：dp[i][j] = min(dp[i - 1][j], dp[i][j - 1],dp[i - 1][j - 1]) + 1， 因为添加了辅助行和辅助列，所以text的索引记得减一。
当word1的第i个字母和word2的第j个字母相同时，他们的编辑距离直接看前面的字符是否匹配。 当word1的第i个字母和word2的第j个字母不同时，他们的编辑距离分三种情况： 1、插入，在word1中的第i 个位置后面插入和word2第j个位置相同的字符，然后编辑距离由 dp[i][j - 1]决定。 2、删除，将word1中的第i个位置的字母删除，然后编辑距离由 dp[i - 1][j]决定。 3、替换，在word1中的第i 个的字母替换为与word2第j个位置相同的字符，然后编辑距离由 dp[i - 1][j - 1]决定。
base case: 添加了辅助行辅助列，相当于在每个字符串的开头添加了一个空字符，所以第一行的值初始化为0，…，m，第一列的值初始化为0，…，n。
class Solution: def minDistance(self, word1, word2): m = len(word1) n = len(word2) if m * n == 0: return m + n dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): dp[i][0] = i for j in range(1, n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = min(dp[i - 1][j], dp[i][j - 1],dp[i - 1][j - 1]) + 1 return dp[-1][-1]2：空间优化 O(2n) 需要两行来进行迭代，因为dp[i][j]需要从dp[i - 1][j - 1]中推导来，不能直接用一行来迭代，只能优化到O(2n)了。
class Solution: def minDistance(self, word1, word2): m = len(word1) n = len(word2) if m * n == 0: return m + n pre = [0] * (n + 1) cur = [0] * (n + 1) for j in range(1, n + 1): pre[j] = j for i in range(1, m + 1): cur[0] = i for j in range(1, n + 1): if word1[i - 1] == word2[j -1]: cur[j] = pre[j - 1] else: cur[j] = min(pre[j], cur[j - 1],pre[j - 1]) + 1 pre = cur[:] return cur[-1]