編輯距離 (Edit Distance)#

編輯距離（Edit Distance，又稱 Levenshtein Distance）回答一個很直觀的問題：要把一個字串改寫成另一個字串，最少得動幾下？它是字串類動態規劃的代表題，背後的思路又能一路延伸到圖論，是體會「不同問題其實是同一個問題」的好例子。

問題#

給兩個字串 A 和 B，把 A 變成 B，最少需要幾次操作？允許的操作有三種，每種各算一步：

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

輸入：A = "horse", B = "ros"
輸出：3
解釋：horse → rorse（把 h 替換成 r）
      rorse → rose （刪除 r）
      rose  → ros  （刪除 e）

這個量度在現實裡到處都是：

• 拼字校正：使用者打錯字時，找出編輯距離最小的字典詞當作建議。
• DNA 比對：兩段基因序列的差異，正好對應插入、刪除、替換三種突變。
• diff 工具：版本控制裡比對兩份檔案、標出增刪行，骨架就是編輯距離。

為什麼只有三種操作？ 插入、刪除、替換已經足以把任何字串變成任何字串。任何更複雜的改寫，都能拆解成這三種基本動作的組合。

狀態定義與轉移#

字串問題的標準切入點，是用「兩個字串各自的前綴」當狀態。

狀態定義：dp[i][j] = 把 A 的前 i 個字元變成 B 的前 j 個字元，所需的最少操作數。

轉移：關鍵在於只看 A 與 B 的最後一個字元 A[i] 與 B[j]。

• 若 A[i] == B[j]：最後一個字元已經對齊，不必動它，直接繼承 dp[i-1][j-1]。
• 若 A[i] != B[j]：必須花一步處理這個差異，從三種操作裡挑最便宜的：
  • 刪除 A 的第 i 個字元 ➡️ 接 dp[i-1][j]
  • 插入 一個字元去補 B 的第 j 個 ➡️ 接 dp[i][j-1]
  • 替換 A 的第 i 個為 B 的第 j 個 ➡️ 接 dp[i-1][j-1]

寫成轉移式：

$$ dp[i][j] = \begin{cases} j, & i = 0 \ i, & j = 0 \ dp[i-1][j-1], & A[i] = B[j] \ 1 + \min\bigl(dp[i-1][j],; dp[i][j-1],; dp[i-1][j-1]\bigr), & A[i] \neq B[j] \end{cases} $$

base case：空字串互轉。 把空字串變成長度 j 的字串，要插入 j 次，所以 dp[0][j] = j；反之把長度 i 的字串清成空字串，要刪除 i 次，所以 dp[i][0] = i。

三條轉移邊各對應什麼？ 把字元一一對齊來想就很清楚：刪除是「A 多了一個字元」，插入是「A 少了一個字元」，替換是「兩邊都有但不一樣」。相等時不耗操作，所以走對角線且不加一。

程式碼實作#

fun minDistance(a: String, b: String): Int {
    val m = a.length
    val n = b.length
    val dp = Array(m + 1) { IntArray(n + 1) }

    // base case：空字串互轉
    for (i in 0..m) dp[i][0] = i  // 刪除 i 次
    for (j in 0..n) dp[0][j] = j  // 插入 j 次

    for (i in 1..m) {
        for (j in 1..n) {
            // 注意：字串索引從 0 起算，故對應字元為 a[i-1]、b[j-1]
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]         // 不需操作
            } else {
                dp[i][j] = 1 + minOf(
                    dp[i - 1][j - 1],               // 替換
                    dp[i - 1][j],                   // 刪除
                    dp[i][j - 1],                   // 插入
                )
            }
        }
    }
    return dp[m][n]
}

填表示意#

以 A = "horse"、B = "ros" 為例，逐格填出的備忘錄如下（列是 A 的前綴，行是 B 的前綴）：

• 第一列、第一行就是 base case（與空字串的距離）。
• 每一格都由左、上、左上三個鄰居推出：字元相等取左上、不等取三者最小加一。
• 右下角 dp[5][3] = 3 就是答案，與前面手動推演的三步一致。

空間優化#

注意轉移式裡，dp[i][j] 只用到上一列（dp[i-1][*]）和當前列左邊（dp[i][j-1]）。也就是說整張表只需保留一列就夠了，空間可以從 O(mn) 降到 O(n)。

唯一的陷阱是：原本的「左上角」dp[i-1][j-1] 在壓成一維後，會被當前列的寫入覆蓋掉，所以要先用一個變數把它暫存起來。

fun minDistance(a: String, b: String): Int {
    val m = a.length
    val n = b.length
    val dp = IntArray(n + 1)

    for (j in 0..n) dp[j] = j  // 第 0 列

    for (i in 1..m) {
        var prev = dp[0]    // 暫存「左上角」dp[i-1][j-1]
        dp[0] = i           // 當前列的第一格 = 刪除 i 次
        for (j in 1..n) {
            val temp = dp[j]  // 覆蓋前先存好，作為下一輪的左上角
            if (a[i - 1] == b[j - 1]) {
                dp[j] = prev
            } else {
                dp[j] = 1 + minOf(prev, dp[j], dp[j - 1])
                // prev = 左上、dp[j] = 上（尚未覆蓋）、dp[j-1] = 左
            }
            prev = temp
        }
    }
    return dp[n]
}

更深的視角：編輯距離就是網格圖上的最短路徑#

把 dp 表想成一張 (m+1) × (n+1) 的網格，每個 dp[i][j] 就是一個格點。從格點 (i-1, j-1)、(i-1, j)、(i, j-1) 走到 (i, j)，分別對應替換、刪除、插入這三條帶權邊：字元相等時對角邊權為 0，其餘所有邊權都是 1。

於是整個問題就變成：從左上角 (0,0) 走到右下角 (m,n)，找一條總權重最小的路徑。 這正是一道單源最短路徑問題。

編輯距離與圖的最短路徑在這裡完全統一了：DP 表上的「逐格遞推」，本質就是在這張有向無環的網格圖上做最短路徑鬆弛。因為邊只往右、下、右下走，圖天然無環，按列順序填表恰好是一種拓撲序——這也說明了為什麼最優子結構在這裡成立：每個格點的最短路徑，都只由它三個前驅格點的最短路徑決定，子問題的最優解能安全地拼成大問題的最優解。

換個角度看，能把「改字串」翻譯成「走網格」，正是演算法裡最值錢的能力：認出陌生問題其實是某個已知模型的化身。

小結#

編輯距離把字串 DP 的核心套路講透了：用兩個前綴當狀態、只盯著末尾字元做決策。更重要的是它示範了如何把一個看似屬於字串的問題，抽象成網格上的最短路徑——當你能在不同領域之間看出這種等價關係，很多新問題其實都只是老問題換了件衣服。