題目：
給定兩個(gè)單詞 word1 和 word2敢订，計(jì)算出將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 王污。
你可以對(duì)一個(gè)單詞進(jìn)行如下三種操作：
1.插入一個(gè)字符
2.刪除一個(gè)字符
3.替換一個(gè)字符
示例 1:
輸入: word1 = "horse", word2 = "ros"
輸出: 3
解釋:
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')
方法一：動(dòng)態(tài)規(guī)劃
思路：
1、dp[i][j] 代表 word1 到 i 位置轉(zhuǎn)換成 word2 到 j 位置需要最少步數(shù)
2楚午、
（1）當(dāng) word1[i] == word2[j]昭齐，dp[i][j] = dp[i-1][j-1]；
（2）當(dāng) word1[i] != word2[j]矾柜，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
（3）其中阱驾，dp[i-1][j-1] 表示替換操作，dp[i-1][j] 表示刪除操作怪蔑，dp[i][j-1] 表示插入操作里覆。
注意，針對(duì)第一行饮睬，第一列要單獨(dú)考慮租谈，我們引入 '' 下圖所示：
第一行篮奄，是 word1 為空變成 word2 最少步數(shù)捆愁，就是插入操作
第一列，是 word2 為空窟却，需要的最少步數(shù)昼丑，就是刪除操作
參考：
力扣解答
時(shí)間復(fù)雜度： O(m * n)
空間復(fù)雜度： O(m * n)
var minDistance = function(word1, word2) {
let m = word1.length;
let n = word2.length;
let dp = Array.from(new Array(m + 1), () => new Array(n + 1).fill(0))
for(let i = 0; i <= m; i++){
dp[i][0] = i;
}
for(let i = 0; i <= n; i++){
dp[0][i] = i;
}
for(let i = 1; i <= m; i++){
for(let j = 1; j <= n; j++){
if(word1[i - 1] === word2[j - 1])
dp[i][j] = dp[i - 1][j - 1]
else
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
}
}
return dp[m][n]
};
