字符串之間的改一下最短要幾步這類問題看著不起眼卻是很多人動態(tài)規(guī)劃之路上繞不過去的一道坎。信息學奧賽一本通里編號 1276 的這道題標題就四個字——編輯距離它講的正是把一個字符串通過插入、刪除、替換三種操作變成另一個字符串求最少操作次數。第一次接觸它的人通常會卡在狀態(tài)怎么定、轉移方程為什么長那樣而刷過幾遍的人又會發(fā)現(xiàn)下標從 0 還是從 1 開始、初始化怎么寫每個細節(jié)都能讓你從樣例通過直接掉到全錯。這篇就把 1276 這道例題從頭到尾拆開講清楚動態(tài)規(guī)劃的設計動機、二維表的手工推演、代碼逐行注釋、以及我踩過的那些坑無論你是剛學完背包的初學者還是想把這道模板題講給別人聽的教練都能從中找到可直接抄作業(yè)的部分。1. 先搞清楚編輯距離到底在解決什么1.1 從打錯字說起問題的直覺理解你在搜索框里輸入 aple系統(tǒng)卻問你是不是想找 apple這背后的核心計算之一就是編輯距離。它的定義非常樸素給定兩個字符串 A 和 B允許三種操作——在任意位置插入一個字符、刪除任意一個字符、把任意一個字符替換成別的字符每次操作算一步問用最少的步數把 A 變成 B 需要多少步。題目 1276 里 A 和 B 的長度都小于 2000最終只要求輸出這個最小步數是一個純數值答案。理解這個問題的關鍵是意識到三種操作之間存在等價和冗余關系。插入一個字符和刪除一個字符互為逆操作替換一個字符有時可以拆成刪一個再插一個但那樣要多花一步所以替換是更劃算的獨立操作。舉個小例子A catB cut只需把中間那個 a 替換成 u一步搞定編輯距離是 1A catB cats末尾插一個 s也是一步。這些簡單的例子看起來毫無難度但一旦字符串變長、字符順序錯位人腦就徹底算不動了這正是需要算法的原因。我特別喜歡拿翻譯來類比把 A 看成原文B 看成譯文編輯距離衡量的是兩者在字符層面有多像。像 kitten 變成 sitting 這類經典例子標準答案是 3k→se→i末尾補 g很多教材都拿它來引入因為它既展示了替換、也展示了插入操作類型齊全短小又好記。1.2 為什么貪心和暴力都行不通有人第一反應是從左往右掃一遍不一樣就改這就是典型的貪心思路。它對少數情況湊巧正確但很快會崩。比如 A abB ba從左掃第 1 位 a 和 b 不同改一次變成 bb再改第二位變成 ba兩步?？蓪嶋H上有更好的解法嗎想想看替換兩次就是 2但如果你刪掉開頭的 a 變成 b再在末尾插一個 a 變成 ba那是 2 步直接交換是不允許的。所以這里 2 是最優(yōu)貪心正好命中了。但換一組A abcdB acbd。從左掃第一位相同第二位 b 和 c 不同若順手改成 c后面就亂了可能要更多步。實際上最優(yōu)是刪掉 b、在 c 后插一個 b共 2 步而貪心容易改成 3 步甚至更多。貪心的根本問題是當前位置改還是刪還是插會影響后面所有字符的對齊方式局部最優(yōu)不代表全局最優(yōu)必須把子問題層層保留下來比較這天然就是動態(tài)規(guī)劃的土壤。暴力搜索更不可行。每一步狀態(tài)都對應一棵分叉樹分支因子是常數級別長度 2000 的情況搜索空間大到無法想象指數級復雜度直接爆掉。所以這道題的正解只有一條動態(tài)規(guī)劃而且是一個二維的、時間 O(n·m)、空間 O(n·m)可優(yōu)化到 O(m)的經典模型。1.3 編輯距離在真實世界里的用武之地別以為這只是競賽題編輯距離是實打實被工業(yè)界廣泛使用的算法。第一類是拼寫糾錯與輸入法候選搜索引擎、手機輸入法在用戶打錯字時會計算輸入串和詞典里每個詞的編輯距離把距離最小的若干詞作為你想找的是不是……推給你。第二類是生物信息學里的 DNA/蛋白質序列比對把堿基或氨基酸看成字符編輯距離及其帶權變體能衡量兩條序列的相似程度是很多比對工具的基礎。第三類是版本控制與文本差異工具比如各種 diff 工具要展示兩段文本改了哪幾行,其行級比較的內核思想也和編輯距離一脈相承。第四類甚至出現(xiàn)在語音識別、抄襲檢測等場景本質都是兩串東西差多少的量化。弄明白這四類應用你就會明白為什么這道例題被反復拿出來講它不只是讓你 AC 一道題而是讓你掌握一個能遷移到無數真實問題里的建模套路。順帶說一句很多人搜這道題會連帶跳出弗洛伊德算法那其實是另一個領域的東西——弗洛伊德用來求圖上任意兩點間最短路是三重循環(huán)松弛編輯距離是字符串對齊的動態(tài)規(guī)劃。兩者唯一相通的地方是都涉及多階段決策取最優(yōu)但狀態(tài)、轉移、場景完全不同別把它們的方程記混了。2. 動態(tài)規(guī)劃設計狀態(tài)定義與轉移方程的來龍去脈2.1 狀態(tài)為什么必須是二維的動態(tài)規(guī)劃第一步永遠是定義狀態(tài)。這道題里答案不是整個 A 變成整個 B一步能算出來的而是由前綴變前綴的子問題疊加而來。原因很簡單字符串的匹配是從左往右對齊的你處理到某個位置時需要同時知道A 已經用掉了前幾個字符B 已經匹配了前幾個字符,這兩個信息缺一不可。于是定義 dp[i][j]把 A 的前 i 個字符變換成 B 的前 j 個字符所需的最少操作次數。注意這里是前 i 個下標含義要牢牢記住很多人后面出錯就是因為把這里的 i、j 理解成了第 i 個字符的下標。為什么是二維而不是一維因為子問題有兩個自由度——A 用多少、B 用多少。一維狀態(tài)沒法同時記錄兩個進度所以二維是最小的必要維度。最終答案自然就是 dp[n][m]其中 n、m 分別是 A、B 的長度。把狀態(tài)想成一張表會更直觀行代表 A 的前綴長度從 0 到 n列代表 B 的前綴長度從 0 到 m。dp[i][j] 就是這張表第 i 行第 j 列的那個格子。填表的過程就是把每個格子用它的左、上、左上三個鄰居推導出來這也解釋了為什么二維表能從左上角一路填到右下角。2.2 三種操作在狀態(tài)轉移里各自對應哪一步理解轉移方程的最好辦法是逆向思考要得到 dp[i][j]考慮最后一步操作作用在哪兒。假設我們已經在湊用 A 的前 i 個字符得到 B 的前 j 個字符看三種操作分別意味著什么。刪除如果 A 的第 i 個字符是多余的把它刪掉那么問題就退化成用 A 的前 i-1 個字符變成 B 的前 j 個字符,代價是 dp[i-1][j] 1。插入如果 B 的第 j 個字符在 A 里沒有對應我們在末尾補一個等價于用 A 的前 i 個字符先湊出 B 的前 j-1 個字符,再補上第 j 個代價是 dp[i][j-1] 1。替換把 A 的第 i 個字符直接改成 B 的第 j 個字符那么兩邊各消耗一個字符退化成用 A 的前 i-1 個字符變成 B 的前 j-1 個字符代價是 dp[i-1][j-1] 1。這三種最后一步的假設覆蓋了所有可能取它們的最小值就是答案。這里有個容易忽略的點當 A 的第 i 個字符和 B 的第 j 個字符本來就相等時替換這一步不需要花費代價甚至比替換更省——直接沿用 dp[i-1][j-1]一個字符完美對齊一步都不用花。2.3 狀態(tài)轉移方程的完整形式與推導把上面的三種情況合在一起就得到了完整的狀態(tài)轉移方程當 A[i] B[j]下標從 1 開始計時dp[i][j] dp[i-1][j-1]當 A[i] ! B[j] 時dp[i][j] min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) 1我先解釋為什么相等時不用考慮另外兩種加操作。假設 A[i] B[j]如果還去嘗試刪除或插入那至少要多花一步而 dp[i-1][j-1] 這個選擇能做到比它們都不差所以直接取它即可無需再取 min。這是一個可以證明的結論省掉了不必要的比較。再說說不相等時為什么是三個里取最小再加一。dp[i-1][j-1] 對應替換dp[i][j-1] 對應插入dp[i-1][j] 對應刪除三者各自代表一種把當前字符對齊掉的思路誰最省就選誰。注意這個方程天然滿足最優(yōu)子結構大的問題答案由小的子問題答案拼出來而且子問題之間沒有循環(huán)依賴保證了按順序填表就能得到正確結果。2.4 邊界條件空串是最重要的起點任何 DP 都要處理邊界這道題的邊界就是其中一個是空串。dp[i][0] 表示把 A 的前 i 個字符變成空串那只能一路刪需要 i 步所以 dp[i][0] i同理 dp[0][j] 表示用空串湊出 B 的前 j 個字符只能一路插需要 j 步所以 dp[0][j] j。dp[0][0] 0 是自然而然的。這兩個邊界看似簡單但它決定了整張表的地基。很多初學者代碼思路完全正確卻因為忘了初始化第一行或第一列導致后面所有格子都算錯樣例過不去。我在下面還會專門拿一節(jié)把初始化的坑講透。這里先記住一句話第一行是從空串到 B 的各前綴第一列是從 A 的各前綴到空串它們的值就是下標本身。理解了這句話初始化就再也不會寫錯。3. 完整代碼實現(xiàn)與逐行拆解3.1 二維 DP 標準寫法與詳細注釋先上最標準、最好理解的二維版本。它是我們的基準版本調通它之后再做空間優(yōu)化才穩(wěn)妥。#include bits/stdc.h using namespace std; int main() { string a, b; cin a b; int n a.size(), m b.size(); // dp[i][j]a 的前 i 個字符變成 b 的前 j 個字符的最少操作數 vectorvectorint dp(n 1, vectorint(m 1, 0)); // 邊界第一列a 的前綴全部刪掉變成空串 for (int i 0; i n; i) dp[i][0] i; // 邊界第一行空串逐個插入得到 b 的前綴 for (int j 0; j m; j) dp[0][j] j; for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i - 1] b[j - 1]) { // 字符相同直接對齊不花代價 dp[i][j] dp[i - 1][j - 1]; } else { // 替換、插入、刪除三選一再補上當前這一步 dp[i][j] min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) 1; } } } cout dp[n][m] endl; return 0; }幾個細節(jié)值得單獨說明。第一字符串用string存儲下標從 0 開始而 dp 表從 1 開始計前綴長度所以訪問字符時統(tǒng)一寫a[i-1]、b[j-1]這個偏移量是坑點重災區(qū)。第二min({...})這種三參數寫法是 C11 以來的初始化列表版本如果評測環(huán)境偏老可以改成min(min(x, y), z)。第三二維數組用vector動態(tài)分配避免大數組爆棧長度 2000 時表有 2001×2001 個格子用int大約 16MB一般題目內存限制下沒問題但如果兩串都接近 2000 且內存卡得緊就需要下面的滾動數組版本。3.2 手工推演一遍樣例把表填出來代碼只是形式真正的理解來自手推。拿一本通 1276 的樣例來走一遍A sfdqxbwB gfdgw。先用邊界把第一行第一列填好然后逐格推進得到下面這張完整的 dp 表行對應 A 的前綴列對應 B 的前綴。dpgfdgw012345s112345f221234d332123q443223x554333b665444w776554右下角 dp[7][5] 4正好是樣例輸出。你可以挑一個格子手動驗算比如 dp[2][2]A 的前兩個字符 sf 變成 B 的前兩個字符 gfs≠g取 min(dp[1][1]1, dp[2][1]2, dp[1][2]2) 1 2但真實情況是 sf→gf 只需把 s 改成 g一步即可為什么表里是 1回頭看看表dp[2][2] 實際填的是 1。這里我要糾正一下剛才的口算dp[1][1] 是 A 的 s 變 B 的 g值確實是 1所以 min 里 dp[1][1]1 最小加一得 2不對等等——字符 s 和 g 不相等時才加 1可對于 dp[2][2]比較的是 a[1]f 和 b[1]f它們相等所以直接取 dp[1][1]1?？催@就是相等分支省掉加一的威力。我們再驗一個不等的情況dp[3][4]A 的前三個 sfd 變 B 的前四個 gfdga[2]db[3]g不相等取 min(dp[2][3]2, dp[3][3]1, dp[2][4]3) 1 1 1 2和表一致。這種手推三五個格子比讀十遍代碼都管用尤其能幫你直觀感受三個鄰居誰最小到底在選什么。3.3 空間優(yōu)化把二維壓成一維當 n、m 都到 2000 甚至更大時二維表雖然能過但空間是 O(n·m)。觀察轉移方程dp[i][j] 只依賴它左邊、上面、左上三個格子也就是說填第 i 行時只需要第 i-1 行的數據更早的行完全沒用了。這就具備了滾動數組壓縮的條件把空間從 O(n·m) 降到 O(m)。#include bits/stdc.h using namespace std; int main() { string a, b; cin a b; int n a.size(), m b.size(); // dp[j] 表示當前處理到 a 的前 i 個字符時變成 b 前 j 個字符的最少操作數 vectorint dp(m 1); for (int j 0; j m; j) dp[j] j; // 相當于第 0 行 for (int i 1; i n; i) { int prev dp[0]; // 保存 dp[i-1][j-1]即左上角 dp[0] i; // 當前行的第 0 列dp[i][0] i for (int j 1; j m; j) { int tmp dp[j]; // 更新前它還是上一行的值即 dp[i-1][j] if (a[i - 1] b[j - 1]) { dp[j] prev; // 對應 dp[i-1][j-1] } else { dp[j] min({prev, dp[j - 1], dp[j]}) 1; } prev tmp; // 為下一列保留左上角 } } cout dp[m] endl; return 0; }這段代碼最容易繞暈的就是三個變量的時序關系我用一句話幫你鎖定更新 dp[j] 之前先把它存進 tmp此時 dp[j-1] 已經是本行第 i 行的新值dp[j] 還是上一行的舊值而 prev 是上一行、上一列的值。三者正好對應狀態(tài)轉移需要的左、上、左上。其中prev tmp放在本輪末尾是為了讓下一列 j1 在使用左上角時拿到的是本行前一列更新前的舊值——這個細節(jié)如果寫反答案會悄悄錯掉但樣例有時候還能過非常陰險。提示滾動數組我強烈建議先在二維版上調通、拿到正確答案再做這一步優(yōu)化并用同一組數據對拍驗證。直接上手一維版一旦出錯你很難判斷是方程錯還是變量時序錯。3.4 輸入輸出與字符串讀入的注意點題目給的是兩行字符串中間可能有空格嗎根據一字通的題意A 和 B 是普通字符串用cin a b就能讀它會自動以空白符分隔。但如果字符串本身可能包含空格某些變體題會這樣就必須用getline。這時常見坑是如果前面用cin讀過數字緩沖區(qū)里會殘留一個換行符getline會讀到空串得先用getchar()或cin.ignore()吃掉那個換行。這道原題不涉及這個但你在做同類型題時要有這根弦。輸出只有一個整數最簡單的cout dp[n][m]即可。有的題會要求如果無解輸出 -1 之類但編輯距離一定是有解的最壞情況就是全刪全插所以不必擔心邊界外的分支。4. 常見坑與調試實錄4.1 下標偏移0 起步與 1 起步的拉鋸戰(zhàn)這是我見過最多人栽的地方。dp 表用 1 表示第一個字符而字符串下標用 0 表示第一個字符兩者差了一位。如果你在代碼里寫成了a[i] b[j]而不是a[i-1] b[j-1]當 i 或 j 取到長度時就會越界輕則答案錯重則程序崩潰。解決辦法有二一是老實用i-1、j-1二是干脆在字符串前面補一個占位符讓兩個下標都從 1 開始對齊比如讀入后執(zhí)行a a; b b;之后統(tǒng)一用a[i]、b[j]。補占位符這個技巧我用了很多年能顯著減少下標錯誤代價是多了兩個字符的內存完全可以忽略。兩種寫法都行關鍵是整段代碼風格統(tǒng)一別一半用一個規(guī)則、一半用另一個規(guī)則。4.2 初始化漏寫或寫錯的連鎖反應初始化的坑有兩種典型形態(tài)。第一種是壓根忘了初始化第一行第一列此時 dp 數組里都是默認的 0結果 dp[i][0] 應該等于 i 卻成了 0整張表全部偏低答案也偏小。第二種是初始化寫對了范圍但寫錯了方向比如把dp[i][0] i寫成了dp[0][i] i行列顛倒在 n≠m 時錯誤會被放大。我的經驗是寫初始化時先在紙上畫一個小表把邊界的值一個個標出來再對著代碼逐行核對尤其是 n 和 m 不相等的時候。如果你用vector且長度寫成了n1和m1記住行的上界是 n、列的上界是 m別寫反。注意dp[i][0] i這一行很容易在重構代碼時被刪掉。養(yǎng)成習慣——凡是二維 DP先肉眼掃一遍第一行第一列有沒有賦值再點運行。4.3 字符比較與 min 的書寫陷阱字符比較本身很簡單但有一個隱藏問題題目里的字符可能是大小寫混合甚至是非 ASCII 的寬字符。原題 1276 都是普通可見字符直接比較沒問題。但如果遇到 Unicode 字符串string里一個字符可能占多個字節(jié)逐個char比較會得到詭異結果這時就需要按碼點切分屬于進階內容本題不涉及。另一個高頻小錯是 min 的參數個數。用min({a, b, c})需要包含algorithm某些環(huán)境下還要注意編譯標準用嵌套min(min(a,b),c)則絕對安全。還有一種錯誤是忘記加 1寫成dp[i][j] min(...)而漏掉 1這種情況下答案會系統(tǒng)性偏小樣例可能湊巧還對但一提交就掛。我調試這類問題的土辦法是挑一個不相等的格子手工算出期望值再打印程序里的實際值一眼就能看出是漏加還是取錯鄰居。4.4 與最長公共子序列的混淆編輯距離和最長公共子序列LCS長得太像了都是二維、都是前綴、都有左上角轉移很多人背著背著就串味。我把區(qū)別釘死在這里LCS 求的是最多能匹配多少個字符相等時dp[i][j] dp[i-1][j-1] 1不相等時取左邊和上面的大者且不加代價編輯距離求的是最少要改多少步相等時dp[i][j] dp[i-1][j-1]不相等時在三個方向里取最小加一。一個求最大、一個求最小一個相等時加一、一個相等時直接沿用。實際上兩者還有一層關系在只允許插入和刪除、不允許替換時編輯距離等于n m - 2 × LCS。把這條關系記住既能幫你區(qū)分兩個模型也能在需要時互相驗證結果。4.5 調試速查表把上面這些坑整理成一張速查表考試或比賽時對著排查效率很高?，F(xiàn)象可能原因排查辦法答案偏小且正好差一個固定值漏寫1或邊界沒初始化手工算一個不等格子的期望值對比程序越界崩潰用了a[i]但 i 可等于 n改成a[i-1]或補占位符n≠m 時全錯nm 時對初始化行列寫反檢查dp[i][0]和dp[0][j]樣例過但提交錯滾動數組 prev 時序錯用二維版對拍小數據答案忽大忽小無規(guī)律混用了 LCS 的轉移式逐個核對相等/不等分支5. 舉一反三從模板題到變形應用5.1 帶權編輯距離當三種操作代價不同一本通這道題默認插入、刪除、替換的代價都是 1但現(xiàn)實中它們并不等值。比如某些場景下刪除很貴、替換相對便宜于是就有了帶權編輯距離給三種操作各設一個代價 w_del、w_ins、w_sub轉移方程變成 dp[i][j] min(dp[i-1][j] w_del, dp[i][j-1] w_ins, dp[i-1][j-1] (相等 ? 0 : w_sub))。改法只有幾處但思路完全一致。理解了基礎版本帶權版本就是順手套公式。更有意思的是當替換代價大于刪除加插入之和時替換操作永遠不會被選模型就退化成純插入刪除的編輯距離正好對應前面提到的 LCS 關系。這個現(xiàn)象說明編輯距離的三種操作并非彼此獨立它們之間存在性價比的權衡設計轉移方程時 min 就是在做這種權衡。5.2 輸出具體操作路徑而不只是次數原題只要次數但很多實際需求要怎么改。做法是在填表的同時記錄每個格子的決策來源是替換、插入還是刪除最后從 dp[n][m] 反向回溯到 dp[0][0]把路徑還原出來?；厮輹r遇到相等格子就一起往左上走遇到不等就根據當時取的 min 來自哪個方向決定輸出哪種操作逆序輸出即可。這個技巧在文本 diff、操作序列生成里非常有用也常被拿來當進階練習。寫回溯代碼有個小坑反推時要重新比較字符是否相等而不是只看到達方向因為替換這個方向在字符恰好相等時其實代表不改動輸出時應該跳過。我一開始就在這里多輸出了一堆無意義的替換改了好幾遍才對。建議回溯時把 dp 表和字符串一起打印出來對照非常直觀。5.3 和其他 DP 模板的橫向對比放到更大的坐標系里看編輯距離屬于序列對齊類動態(tài)規(guī)劃和 LCS、最長上升子序列、正則匹配、通配符匹配、最短公共超序列這幾類共享同一套骨架二維狀態(tài)、前綴劃分、左/上/左上轉移。把這幾個模型聚在一起練你會發(fā)現(xiàn)它們的差別主要就三點——相等時加不加一、不等時取 max 還是 min、要不要額外加常數。抓住這三點一整類題就打通了。模型相等時不等時目標編輯距離取左上三方取 min 再 1最小操作數最長公共子序列左上 1左右取 max最長匹配長度最短公共超序列左上 1上下取 min 再 1最短合并長度通配符匹配視規(guī)則而定上下左取并能否匹配我自己復習 DP 時習慣把這些方程列成一張對照表貼在桌角做題卡殼時掃一眼往往立刻就能定位是哪個分支記錯了。這種把同類模型打包記憶的方式比一道一道孤立地刷要高效得多尤其適合準備競賽的同學在沖刺階段快速回憶。6. 我在這道題上踩過的那些坑說點書本上不太會寫的東西。我第一次AC這道題花的時間遠超預期原因不是不會方程而是連續(xù)栽在下標的坑里。當時我圖省事直接寫了a[i] b[j]小數據沒事一放大到臨界長度就段錯誤調試工具一掛我才發(fā)現(xiàn) i 走到了 n。后來我養(yǎng)成了一個近乎強迫癥的習慣只要寫二維 DP先在草稿紙畫個 3×3 的小表把邊界和第一個內格的值算出來代碼跑完先打印這張小表對照對了再放大數據。這個動作多花兩分鐘能省掉的調試時間往往是半小時起步。第二個體會是關于對拍的。滾動數組優(yōu)化那次我寫得挺順樣例也過了結果交上去只過了三成測試點。后來我寫了個小腳本隨機生成幾組長度不超過 8 的字符串分別跑二維版和一維版幾百組一比就發(fā)現(xiàn)有兩組對不上。定位到具體是 prev 更新時機錯了——在某些 j 位置它拿了本行的新值當左上角導致個別格子偏小。對拍這種暴力版 vs 優(yōu)化版的交叉驗證是我認為性價比最高的調試手段強烈建議每個做 DP 優(yōu)化的人都備一套。最后分享一個記憶訣竅。狀態(tài)轉移的三個方向我用一句話記左上管改上管刪左管插。左上角 dp[i-1][j-1] 對應把當前這對字符替換掉上面 dp[i-1][j] 對應刪掉 A 的一個字符左邊 dp[i][j-1] 對應在 A 里插一個字符補齊 B。順著這句話不用死記方程也能在考場上現(xiàn)推出來。至于邊界還是那句老話——第一行是第一串空串往 B 里插第一列是 A 往空串里刪值就是下標本身。把這兩句口訣內化這道 1276 以及它的一大票親戚題基本就穩(wěn)了。