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