题目描述：
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
题解：
题目给定了两个单词，设为 A 和 B，这样我们就能够六种操作方法。
但我们可以发现，如果我们有单词 A 和单词 B：
对单词 A 删除一个字符和对单词 B 插入一个字符是等价的。例如当单词 A 为 doge，单词 B 为 dog 时，我们既可以删除单词 A 的最后一个字符 e，得到相同的 dog，也可以在单词 B 末尾添加一个字符 e，得到相同的 doge；
同理，对单词 B 删除一个字符和对单词 A 插入一个字符也是等价的；
对单词 A 替换一个字符和对单词 B 替换一个字符是等价的。例如当单词 A 为 bat，单词 B 为 cat 时，我们修改单词 A 的第一个字母 b -> c，和修改单词 B 的第一个字母 c -> b 是等价的。
这样一来，本质不同的操作实际上只有三种：
在单词 A 中插入一个字符；
在单词 B 中插入一个字符；
修改单词 A 的一个字符。
这样一来，我们就可以把原问题转化为规模较小的子问题。我们用 A = horse，B = ros 作为例子，来看一看是如何把这个问题转化为规模较小的若干子问题的。
在单词 A 中插入一个字符：如果我们知道 horse 到 ro 的编辑距离为 a，那么显然 horse 到 ros 的编辑距离不会超过 a + 1。这是因为我们可以在 a 次操作后将 horse 和 ro 变为相同的字符串，只需要额外的 1 次操作，在单词 A 的末尾添加字符 s，就能在 a + 1 次操作后将 horse 和 ro 变为相同的字符串；
在单词 B 中插入一个字符：如果我们知道 hors 到 ros 的编辑距离为 b，那么显然 horse 到 ros 的编辑距离不会超过 b + 1，原因同上；
修改单词 A 的一个字符：如果我们知道 hors 到 ro 的编辑距离为 c，那么显然 horse 到 ros 的编辑距离不会超过 c + 1，原因同上。
归纳一下：
① 固定一边字符，对于子问题，状态转换只有增加和修改，但子问题当中还是有删除操作。
② A 或 B 字符串新增一个字符，或两边同时新增一个字符，且新增字符不同，操作均加一。
③当两边同时修改状态时，即两边同时新增一个字符，且新增字符相同，无需新增操作数，类似回文串操作。
④状态添加 截止 同时完成A、B字符。
图示：
1.边界状态初始化
2. B[i]不等于A[j] 时，从dp [i-1][j-1]状态，到dp[i][j]，进行字符修改，+1
3.或者向右或向下，进行状态转移，进行字符添加，+1
4.最小添加数为 上述三种情况最小值；
5.当B[i]等于A[j] 时，从dp [i-1][j-1]状态，到dp[i][j]状态，不需要修改或新增，+0；
6.状态转移 截止 同时完成A、B字符，输出dp[-1][-1]。
代码：
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
#创建二维dp
m = len(word1)
n = len(word2)
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(1,n+1):
for j in range(1,m+1):
if word1[j-1]!=word2[i-1]:
dp[i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1
else:
dp[i][j] = dp[i-1][j-1]
return dp[-1][-1]
