dp 力扣 72. 編輯距離

給你兩個單詞 word1 和 word2，請你計算出將 word1 轉換成 word2 所使用的最少運算元 。

你可以對一個單詞進行如下三種操作：

插入一個字元
刪除一個字元
替換一個字元

範例 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’)

思路：
挨個比較字串中字元，若相等則等同比較下一位
若不相等，依次比較插入刪除和替換對編輯距離的影響。

程式碼：

class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        int m = word1.length();
        int n = word2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i < m + 1; i++)
        {
            dp[i][0] = i;
        }
        for (int i = 1; i < n + 1; i++)
        {
            dp[0][i] = i;
        }
        for (int i = 1; i < m + 1; i++)
        {
            for (int j = 1; j < n + 1; j++)
            {
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min(dp[i - 1][j - 1] + 1/*替換*/,
                     min(dp[i - 1][j] + 1/*刪除*/, 
                     dp[i][j - 1] + 1/*插入*/));
            }
        }
        return dp[m][n];
    }
};

來搞一波動態規劃~~~