☆打卡算法☆LeetCode 72、编辑距离 算法解析

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

示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

public class Solution {
    public int MinDistance(string w1, string w2) {
        //【dp数组定义】w1转为w2所需的最小操作数
        int[,] dp = new int[w1.Length + 1, w2.Length + 1];
        //【初始化】
        for (int i = 0; i <= w1.Length; i++) dp[i, 0] = i;
        for (int j = 0; j <= w2.Length; j++) dp[0, j] = j;
        //【状态转移】
        for (int i = 1; i <= w1.Length; i++)
        {
            for (int j = 1; j <= w2.Length; j++)
            {
                if (w1[i - 1] == w2[j - 1])
                    //如果最后一位相等，最少操作数无影响
                    dp[i, j] = dp[i - 1, j - 1];
                else
                    //如果不相等，到d[i,j]一共有3种状态，取最小：替换、w1新增w2的最后1位、w2新增w1的最后1位
                    dp[i, j] = Math.Min(dp[i - 1, j - 1], Math.Min(dp[i - 1, j], dp[i, j - 1])) + 1;
            }
        }
        return dp[w1.Length, w2.Length];
    }
}