(动态规划) LeetCode72. 编辑距离

题目：
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
1.插入一个字符
2.删除一个字符
3.替换一个字符

示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

方法一：动态规划
思路：

1、dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
2、
（1）当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
（2）当 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] 表示插入操作。
注意，针对第一行，第一列要单独考虑，我们引入 '' 下图所示：

第一行，是 word1 为空变成 word2 最少步数，就是插入操作
第一列，是 word2 为空，需要的最少步数，就是删除操作
参考：
力扣解答

时间复杂度： O(m * n)
空间复杂度： 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]  
};