题目

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例

输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

解析

这道题和之前的题目相比，之前的都是只能删除，这道题还可以插入和替换，情况相比之前的多了几种；还是用动归五部曲分析下：
1.确定dp数组及其含义
dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。至于为什么是i-1这一系列的，前面都说过了，主要就是为了代码好写以及初始化方便；
2.确定递推公式
还是先大致分为以下情况：
if word1(i-1) == word2(j-1)
这种情况下dp[i][j] = dp[i - 1][j - 1];为什么会等于上一步呢，因为此时两个值已经相等了，那么就不用操作了，直接等于上一步的结果就可以
if word1(i-1) ！= word2(j-1)，此时会再细分为增、删、改三种情况，而这几种情况下，可以划分为以下几种操作：
一、word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离的基础上，再加上这个操作；即dp[i][j] = dp[i-1][j] + 1
二、word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离的基础上，再加上这个操作；即dp[i][j] = dp[i][j-1] + 1
与此同时，对于添加操作，一个上面的添加其实相当于另一个的删除，是一样的
三、替换元素，比如说，从word1中要将word1[i-1]替换成word2[i-1]的元素，首先已知：
if (word1[i - 1] == word2[j - 1]) 时 dp[i][j] = dp[i - 1][j - 1]
那么再加上这个替换的操作，就是 dp[i][j] = dp[i - 1][j - 1] + 1;
综合上面的三个操作，取最小值即可
3.初始化
本题的初始化和上一道题的一样，大概的意思就是从一个字符串删到空串的值，后面再补充具体的逻辑

func minDistance(word1 string, word2 string) int {m := len(word1)n := len(word2)dp := make([][]int, m+1)for i := range dp {dp[i] = make([]int, n+1)}// 初始化for i := range dp {dp[i][0] = i}for j := range dp[0] {dp[0][j] = j}for i := 1; i <= m; i++ {for j := 1; j <= n; j++ {if word1[i-1] == word2[j-1] {dp[i][j] = dp[i-1][j-1]} else {dp[i][j] = min(min(dp[i-1][j] + 1, dp[i][j-1] + 1), dp[i-1][j-1] + 1)}}}return dp[m][n]
}func min(a,b int) int {if a < b {return a}return b
}