72 Edit Distance

确定将一个单词转换为另一个单词的最小操作数，只有增/删/替换操作

如果长度为i和j的字符串最后元素相等，dp[i][j] = dp[i - 1][j - 1]
如果长度为i和j的字符串最后元素不相等，dp[i][j] = Math.min(dp[i][j - 1] , dp[i - 1][j], dp[i - 1][j - 1]) + 1
首先把第一行第一列确定

动态规划，faster than 52%

需要注意的是dp的长度要比word长度大1，这是为了考虑空字符串的情况，并且判决的时候要用[i - 1][j - 1] 判决，因为前述考虑了空字符串的情况

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    var m = word1.length + 1
    var n = word2.length + 1
    var dp = Array(m).fill().map(item => Array(m).fill(0))
    for(var i = 0; i < m; i++){
        dp[i][0] = i
    }
    for(var j = 0; j < n; j++){
        dp[0][j] = j
    }
    for(var i = 1; i < m; i++){
        for(var 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], dp[i][j - 1], dp[i - 1][j - 1]) + 1
        }
    }
    return dp[m - 1][n - 1]
};