思路1 dp

D[i][j] 表示 word1 的前 i 个字母和 word2 的前 j 个字母之间的编辑距离。

当word[i] == word[j]时， d[i][j] = d[i-1][j-1]，因为新加上的字符相等，无需编辑

当word[i] != word[j]时，有三种情况

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

• dp[i-1][j-1]到dp[i][j]需要进行一次替换。因为在i-1和j-1的时候，两个字符串已经完成编辑相等了。两个words各加一个新字符，再进行一次转换就行了

• dp[i-1][j]到dp[i][j]，需要删除一个字符。i-1和j已经是相等的了，word1再新加一个字符。把这个新加的字符删掉还是相等

• dp[i][j-1]到dp[i][j]，需要插入一个字符。因为word2新加了一个字符，word1也需要插入新加的字符。

另外有编辑情况dp[0][j] = j, dp[i][0] = i。表示空字符串和非空字符串之间的转换