編輯距離（edit distance）
/ Levenshtein = LEV-en-shtine /
編輯距離藉由計算「把一個字串變成另一個所需的最少單字元編輯次數」來衡量兩個字串有多不同。允許的編輯有插入一個字元、刪除一個字元、把一個字元替換成另一個，每個各花 1。所以從 'kitten' 到 'sitting' 的編輯距離是 3：替換 k->s、替換 e->i、插入一個 g。這個數字是拼字檢查器（「你是不是要找…？」）、模糊搜尋、DNA 比對背後的依據，因為它直觀地捕捉了兩個序列有多接近。
這個動態規劃逐前綴地比較兩字串。令 dp[i][j] 為 A 前 i 個字元與 B 前 j 個字元的編輯距離。若當前的末字元相符（A[i] = B[j]），它們不需編輯，於是 dp[i][j] = dp[i-1][j-1]。若相異，你為三種編輯之一付 1 並取最便宜者：dp[i][j] = 1 + min( dp[i-1][j] 對應刪除 A[i]、dp[i][j-1] 對應插入 B[j]、dp[i-1][j-1] 對應替換 )。基底情況表示把字串變成空字串或從空字串變來，每個剩餘字元花一次編輯：dp[i][0] = i（刪光 A 前 i 個）與 dp[0][j] = j（插入 B 前 j 個）。逐列由上而下、列內由左而右地填表，花 O(mn) 時間與 O(mn) 空間，若你只要那個數字，可用滾動兩列陣列降到 O(min(m, n)) 空間。
編輯距離是最長共同子序列的近親——兩者都比較前綴、都看末字元——但它最小化的是改動的成本，而非最大化一致的長度，把這一對並排來看很有用。兩個誠實的提醒。第一，這個答案在數學意義上是一個真正的距離（它對稱且滿足三角不等式），這正是它作為相似度分數表現良好的原因。第二，這個基本版本每次編輯收 1；採用不同成本的變體（替換花 2，或如生物對齊中按字元對加權）只是改變轉移中相加的數，但同一個動態規劃形狀延續不變。
'kitten' 到 'sitting'：表一路建到 dp[6][7] = 3。回溯顯示替換 k->s、保留 i, t, t、替換 e->i、保留 n、插入 g。每個花 1 的對角步驟是替換；最後那個非對角步驟是插入的 g。
相符不花成本；否則為刪除、插入、替換中最便宜者付 1。
基本編輯距離每次編輯收 1 並允許替換；若你禁止替換（只准插入和刪除），答案就轉而與最長共同子序列相關。務必釐清問題實際允許哪些編輯操作與成本。