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

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

狀態定義

dp[i][j]：word1 前 i 字符轉換為 word2 前 j 字符的最小代價。

轉移方程

對齊尾部三種情況：

• 刪除 word1[i-1]：dp[i-1][j] + 1
• 插入 word2[j-1]：dp[i][j-1] + 1
• 替換/保留：dp[i-1][j-1] + (word1[i-1]==word2[j-1] ? 0 : 1)

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + cost)

邊界條件

• dp[0][0] = 0
• dp[i][0] = i（全刪除）
• dp[0][j] = j（全插入）

Java 完整實現（底向上 + 空間優化）

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

複雜度

• 時間：O(mn)
• 空間：O(min(m,n))（滾動數組）

應用

• 拼寫檢查、DNA 序列比對、版本控制差異檢測。
• Lucene/ElasticSearch 模糊查詢底層即編輯距離。