LeetCode Edit Distance：編輯距離動態規劃詳解

題目描述

給定兩單詞 word1、word2，允許插入、刪除、替換三種操作（每步代價 1），求將 word1 轉換為 word2 的最小步數。

範例："mart" → "karma" 輸出 3。

動態規劃解法

定義 dp[i][j] 為 word1[0..i] 轉換為 word2[0..j] 的最小步數（下標從 0 開始）。

狀態轉移：

• 若 word1[i] == word2[j]：dp[i][j] = dp[i-1][j-1]（無需操作）。
• 否則取三種操作的最小值 +1：
  • 替換：dp[i-1][j-1] + 1
  • 刪除 word1[i]：dp[i-1][j] + 1
  • 插入 word2[j]：dp[i][j-1] + 1

邊界初始化：

• dp[i][0] = i+1（若首字符不匹配）或 i（匹配），實際上 dp[i][0] 為將 word1[0..i] 變為 word2[0] 的代價。
• 同理 dp[0][j]。

標準做法擴展矩陣至 (m+1)×(n+1)，dp[0][0]=0，dp[i][0]=i，dp[0][j]=j，避免邊界討論。

參考代碼 (Java，標準 (m+1)×(n+1) 寫法)

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int j = 0; j <= n; ++j) dp[0][j] = j;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1.charAt(i-1) == word2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
            }
        }
        return dp[m][n];
    }
}

空間優化 (1D DP)

只需保留上一行與當前行，使用 prev 變量暫存 dp[i-1][j-1]。