第一次在題庫(kù)里刷到 P1006 傳紙條 的時(shí)候我的第一反應(yīng)是這不就是求兩條路徑的最大權(quán)值和嗎直接貪心先找一條最優(yōu)路徑再找第二條不就行了。直到自己動(dòng)手寫了一版貪心發(fā)現(xiàn)樣例都過(guò)不了。第一條路走完第二條路被擠在角落里兩個(gè)“局部最優(yōu)”加起來(lái)遠(yuǎn)不是全局最優(yōu)。后來(lái)去翻各種題解看到“雙狀態(tài)DP”這個(gè)說(shuō)法才意識(shí)到這道題真正要學(xué)的不是路徑搜索而是怎么把“兩個(gè)人同時(shí)移動(dòng)”這個(gè)瞬間狀態(tài)合理地編碼進(jìn)DP數(shù)組。這道題在很多算法題庫(kù)里都有適合剛學(xué)完區(qū)間DP、準(zhǔn)備進(jìn)階網(wǎng)格DP的讀者也適合想搞清楚“為什么四維能壓成三維”的人。下面我把整個(gè)推導(dǎo)、踩坑和代碼實(shí)現(xiàn)完整梳理一遍。1. 一張紙條怎么變成了兩條不重合的路徑1.1 傳紙條故事的模型化題目背景是 m 行 n 列的座位矩陣每個(gè)格子里有一個(gè)同學(xué)每個(gè)同學(xué)有一個(gè)“好感度”數(shù)值。紙條從左上角傳出沿著只能向右或向下的方向經(jīng)過(guò)若干同學(xué)后到達(dá)右下角然后還要從右下角原路傳回左上角。整個(gè)過(guò)程中除了起點(diǎn)和終點(diǎn)同一個(gè)同學(xué)不能被重復(fù)傳遞。把“傳過(guò)去再傳回來(lái)”翻譯成算法語(yǔ)言時(shí)大多數(shù)人會(huì)犯一個(gè)方向上的思維定式去程是從左上到右下回程是從右下到左上方向相反看起來(lái)得設(shè)計(jì)兩套狀態(tài)。關(guān)鍵轉(zhuǎn)換在于把回程路徑沿著時(shí)間倒過(guò)來(lái)看。一條從右下到左上的路徑倒序之后就變成一條從左上到右下的路徑。也就是說(shuō)去程和回程可以統(tǒng)一成兩條從左上角到右下角、方向完全一致的路徑。題目里的“不能重復(fù)經(jīng)過(guò)同一個(gè)同學(xué)”就變成這兩條路徑除了起點(diǎn)和終點(diǎn)之外不能共享任何格子。這一步模型抽象是整個(gè)題目的地基。很多題解直接說(shuō)“兩條路徑”但沒(méi)有解釋為什么能這樣等價(jià)轉(zhuǎn)換。我在第一次做的時(shí)候就是因?yàn)闆](méi)想通方向問(wèn)題一直糾結(jié)要不要分別記錄兩條路徑的方向走了不少?gòu)澛贰?.2 為什么“先找一條最優(yōu)路再找第二條”會(huì)翻車既然變成了兩條路徑一個(gè)很自然的想法是分兩步做先用最短路/DP找出權(quán)值和最大的一條路徑把這條路徑上的格子標(biāo)記為不可用再找第二條。這種貪心思路在不少題目里都能用但在傳紙條這里會(huì)翻車。原因很簡(jiǎn)單第一條路徑取了全局最優(yōu)但它可能把整個(gè)矩陣?yán)铩皹屑~位置”的格子全部占掉導(dǎo)致第二條路徑只能繞很遠(yuǎn)的路收益斷崖式下降。局部最優(yōu)的兩段拼起來(lái)并不等于整體最優(yōu)。舉個(gè)例子矩陣中間有一個(gè)高權(quán)值格子兩條路徑本來(lái)可以分別從它的兩側(cè)繞過(guò)讓總收益覆蓋更多格子但貪心會(huì)讓第一條路徑直接踩過(guò)這個(gè)高權(quán)值格子第二條就被迫繞到邊緣整體收益反而不如兩條路徑都稍微“彎腰”的方案。所以傳紙條不能拆成兩個(gè)獨(dú)立子問(wèn)題必須把兩條路徑當(dāng)成一個(gè)整體在同一套狀態(tài)里同步規(guī)劃。這也是雙狀態(tài)DP必須“同步”的根本原因。2. 狀態(tài)設(shè)計(jì)四維坐標(biāo)為什么能砍成三個(gè)數(shù)2.1 從四維DP出發(fā)如果完全不考慮優(yōu)化最直覺(jué)的狀態(tài)設(shè)計(jì)是四維dp[i][j][k][l] 表示第一條路走到了 (i,j)第二條路走到了 (k,l) 時(shí)已經(jīng)累計(jì)的最大權(quán)值和。轉(zhuǎn)移時(shí)每個(gè)人都可以從上方或左方過(guò)來(lái)組合起來(lái)就是四種前驅(qū)第一條從上方第二條從上方第一條從上方第二條從左方第一條從左方第二條從上方第一條從左方第二條從左方。這個(gè)模型本身是自洽的m、n 最多 50 時(shí)四維狀態(tài)數(shù)約 50^4 625 萬(wàn)勉強(qiáng)也能跑。但它有兩個(gè)問(wèn)題一是浪費(fèi)了大量不可能出現(xiàn)的狀態(tài)二是判重邏輯非常別扭——我并不知道兩人是不是“先后”經(jīng)過(guò)了同一個(gè)格子。真正讓我決定放棄四維寫法的是代碼里那個(gè)判重想判斷兩條路徑有沒(méi)有共享某個(gè)格子得把整條路徑的歷史信息都記住才行。顯然這不適合用 DP 解決。2.2 同步不變量行列相等四維DP最大的漏洞是它沒(méi)有利用“兩個(gè)人同時(shí)出發(fā)、每步都走一格”這個(gè)條件。設(shè)當(dāng)前兩人都已經(jīng)走了 s-1 步也可以定義走了 s 步時(shí)間是一致的。因?yàn)槊坎街荒芟蛴一蛳蛳滤缘谝粋€(gè)人所在格子的行加列永遠(yuǎn)等于第二個(gè)人所在格子的行加列這個(gè)公共值就是當(dāng)前時(shí)刻的“步數(shù)指針”i j k l s既然行加列恒定那么四個(gè)坐標(biāo)里其實(shí)只有三個(gè)自由度。知道 s 和某人的行坐標(biāo)就能算出他的列坐標(biāo)。于是狀態(tài)可以縮成三維dp[s][i][k]s 表示當(dāng)前的行列之和i 是第一個(gè)人的行坐標(biāo)k 是第二個(gè)人的行坐標(biāo)。兩個(gè)人的列坐標(biāo)分別由 s-i 和 s-k 推導(dǎo)出來(lái)。這個(gè)壓縮沒(méi)有丟失任何信息。因?yàn)槁窂街辉试S向右或向下合法位置的坐標(biāo)始終滿足行加列等于固定值不存在需要額外記住列坐標(biāo)才能區(qū)分的歧義狀態(tài)。2.3 壓縮帶來(lái)的額外好處判重變簡(jiǎn)單壓縮不只是省空間它讓“判斷兩人是否站在同一格”這件事變得極其簡(jiǎn)單。在同一個(gè) s 時(shí)刻如果兩個(gè)人的行坐標(biāo)相同也就是 i k那么他們的列坐標(biāo)也必然相同s - i s - k這意味著兩人當(dāng)前站在同一個(gè)格子里。于是“兩條路徑不能共享格子”這個(gè)條件在同步DP里被翻譯成一句非常干凈的代碼當(dāng) i k 且 s ! mn 時(shí)這個(gè)狀態(tài)非法直接跳過(guò)。起點(diǎn)和終點(diǎn)允許兩人相遇所以單獨(dú)放行終點(diǎn)即可。我在理解這個(gè)判重時(shí)最大的感慨是狀態(tài)的壓縮順序應(yīng)該反過(guò)來(lái)想。不是因?yàn)橐獕嚎s才故意選三維而是因?yàn)榘l(fā)現(xiàn)了“行加列相等”這個(gè)不變量三維狀態(tài)本來(lái)就是問(wèn)題內(nèi)在的結(jié)構(gòu)。用合適的坐標(biāo)系描述問(wèn)題很多邊界條件會(huì)自動(dòng)變得清晰。3. 四條前驅(qū)分支遞推式從哪來(lái)邊界怎么卡3.1 上一步的四種來(lái)源現(xiàn)在推導(dǎo)轉(zhuǎn)移方程。dp[s][i][k] 表示當(dāng)前兩個(gè)人分別在 (i, s-i) 和 (k, s-k)?；氐缴弦粫r(shí)刻 s-1看第一個(gè)人這一步做了什么如果這一步向右走行坐標(biāo)不變上一步行坐標(biāo)仍然為 i列坐標(biāo)為 (s-1)-i如果這一步向下走行坐標(biāo)加 1上一步行坐標(biāo)就是 i-1列坐標(biāo)為 (s-1)-(i-1)s-i。第二個(gè)人同理上一步行坐標(biāo)要么是 k要么是 k-1。把兩個(gè)人的選擇組合起來(lái)得到四個(gè)前驅(qū)狀態(tài)dp[s-1][i][k]、dp[s-1][i-1][k]、dp[s-1][i][k-1]、dp[s-1][i-1][k-1]取這四個(gè)值的最大值加上當(dāng)前位置的權(quán)值就是 dp[s][i][k]。這里我用的行坐標(biāo)是 r代碼里寫作 r1、r2。如果你習(xí)慣用列坐標(biāo)寫推導(dǎo)完全對(duì)稱但一定要全程保持一致不要在同一個(gè)程序里混用行坐標(biāo)和列坐標(biāo)否則很容易在中途把索引寫亂。3.2 權(quán)值累加與同格判重當(dāng)前位置的權(quán)值貢獻(xiàn)分為兩種情況。正常情況下第一個(gè)人落在 (i, s-i)第二個(gè)人落在 (k, s-k)貢獻(xiàn)為 a[i][s-i] a[k][s-k]。但 i k 時(shí)兩人站在同一格必須只計(jì)一次。于是完整轉(zhuǎn)移可以寫成val a[i][s-i] if (i ! k) val a[k][s-k] dp[s][i][k] max(前四個(gè)前驅(qū)) val再加上一條合法性過(guò)濾如果 i k 且 s ! mn說(shuō)明兩人在中間某個(gè)格子碰頭了這個(gè)狀態(tài)非法。不過(guò)要注意起點(diǎn)在 s2 時(shí)已經(jīng)初始化且 smn 的終點(diǎn)是合法碰頭點(diǎn)過(guò)濾時(shí)不能把終點(diǎn)也干掉。很多人會(huì)把“重合時(shí)只計(jì)一次”和“重合時(shí)直接跳過(guò)”搞混。前者是方格取數(shù)的邏輯后者才是傳紙條的邏輯。傳紙條里兩人中間碰頭就是非法不是少計(jì)一次權(quán)值的問(wèn)題是整條路徑都不能要。3.3 為什么不需要擔(dān)心“先后踏進(jìn)同一個(gè)格子”這是最容易被追問(wèn)也是最值得展開的一點(diǎn)。同步DP里的判重只檢查了同一時(shí)刻兩人是否站在同一格那如果第一條路徑先經(jīng)過(guò)格子 P第二條路徑后經(jīng)過(guò)格子 P這算不算路徑相交會(huì)不會(huì)被漏掉答案是這種方案確實(shí)在同步DP里不會(huì)被直接發(fā)現(xiàn)但它不影響答案。原因是一條經(jīng)典的重排定理如果兩條從左上到右下的路徑在某個(gè)格子 P 相交那么在 P 點(diǎn)之后把第一條路徑的后半段和第二條路徑的后半段互換得到的兩條新路徑仍然都是從左上到右下、只向右向下走的合法路徑。P 之后的路徑段長(zhǎng)度是固定的互換后總權(quán)值完全不變但公共格的數(shù)量會(huì)減少。重復(fù)這個(gè)交換過(guò)程最后一定能得到一組除起點(diǎn)終點(diǎn)外互不相交的路徑而且權(quán)值不劣于原方案。既然存在一組最優(yōu)解中的兩條路徑互不相交那么同步DP只需枚舉“任何時(shí)刻都不在同一格”的路徑組就能覆蓋最優(yōu)答案。這個(gè)結(jié)論是傳紙條、方格取數(shù)這類題能用同步DP的理論基礎(chǔ)。3.4 用手算小例子驗(yàn)證邏輯光講公式容易飄我用一個(gè) 3x3 的矩陣做個(gè)局部演算。矩陣如下1 2 3 4 5 6 7 8 9s2 時(shí)只有 dp[2][1][1] 1也就是兩個(gè)人都站在起點(diǎn) (1,1)權(quán)值只計(jì)一次。s3 時(shí)行的合法范圍是 1 到 2因?yàn)樾屑恿械扔?3。合法轉(zhuǎn)移有兩個(gè)dp[3][1][2]第一個(gè)人 (1,2)、第二個(gè)人 (2,1)權(quán)值 1 2 4 7dp[3][2][1]權(quán)值也是 7對(duì)稱。ik 的 (1,1) 和 (2,2) 狀態(tài)全被跳過(guò)。這兩個(gè) 7 會(huì)繼續(xù)參與 s4 的計(jì)算后面每層都只從四個(gè)前驅(qū)中取最大值擴(kuò)展。這樣一個(gè)簡(jiǎn)單例子就能確認(rèn)坐標(biāo)換算、前驅(qū)枚舉和判重邏輯沒(méi)有跑偏。4. 完整代碼與四個(gè)容易踩碎的細(xì)節(jié)4.1 三維DP的標(biāo)準(zhǔn)寫法我習(xí)慣把行坐標(biāo)記作 r列坐標(biāo)通過(guò) s-r 算出。完整代碼貼在下面注釋寫的是最容易踩坑的位置#include bits/stdc.h using namespace std; const int N 55; const int INF 0x3f3f3f3f; int a[N][N]; int dp[N * 2][N][N]; int main() { int m, n; cin m n; for (int i 1; i m; i) for (int j 1; j n; j) cin a[i][j]; memset(dp, -INF, sizeof(dp)); // s 2 對(duì)應(yīng)兩個(gè)人都站在起點(diǎn) (1, 1) // 起點(diǎn)的權(quán)值只計(jì)一次 dp[2][1][1] a[1][1]; for (int s 3; s m n; s) { // 行 r 的合法范圍由 1 s - r n 推出 int r_lo max(1, s - n); int r_hi min(m, s - 1); for (int r1 r_lo; r1 r_hi; r1) { for (int r2 r_lo; r2 r_hi; r2) { // 中間碰頭非法終點(diǎn)允許碰頭 if (r1 r2 s ! m n) continue; int c1 s - r1; int c2 s - r2; // 當(dāng)前位置權(quán)值重疊格只計(jì)一次 int val a[r1][c1]; if (r1 ! r2) val a[r2][c2]; // 四條前驅(qū)分支 int best dp[s - 1][r1][r2]; best max(best, dp[s - 1][r1 - 1][r2]); best max(best, dp[s - 1][r1][r2 - 1]); best max(best, dp[s - 1][r1 - 1][r2 - 1]); dp[s][r1][r2] best val; } } } // 終點(diǎn)是 (m, n)s m n兩人的行坐標(biāo)都是 m cout dp[m n][m][m] endl; return 0; }代碼里最需要注意的一點(diǎn)是 r_lo 和 r_hi 的推導(dǎo)。很多人圖省事直接寫成 1 到 m然后靠里面的 if 判斷越界也能過(guò)但那種寫法容易讀著讀著就忘記自己還開著越界保護(hù)。我更推薦把循環(huán)邊界直接卡對(duì)這樣后面加滾動(dòng)數(shù)組時(shí)也更不容易出錯(cuò)。4.2 滾動(dòng)數(shù)組優(yōu)化后的寫法三維版本的 dp 數(shù)組大小約 100 * 50 * 50其實(shí)不算大。但如果 m、n 繼續(xù)增大或者以后遇到類似的三維網(wǎng)格DP滾動(dòng)數(shù)組就是必須掌握的技巧。觀察轉(zhuǎn)移可以發(fā)現(xiàn)dp[s] 只依賴 dp[s-1]更早的層永遠(yuǎn)不會(huì)再用到所以可以只保留兩層int dp[2][N][N]; // cur 表示當(dāng)前層 int cur 0; memset(dp, -INF, sizeof(dp)); dp[cur][1][1] a[1][1]; // s 2 for (int s 3; s m n; s) { int nxt cur ^ 1; memset(dp[nxt], -INF, sizeof(dp[nxt])); int r_lo max(1, s - n); int r_hi min(m, s - 1); for (int r1 r_lo; r1 r_hi; r1) { for (int r2 r_lo; r2 r_hi; r2) { if (r1 r2 s ! m n) continue; int c1 s - r1; int c2 s - r2; int val a[r1][c1]; if (r1 ! r2) val a[r2][c2]; int best dp[cur][r1][r2]; best max(best, dp[cur][r1 - 1][r2]); best max(best, dp[cur][r1][r2 - 1]); best max(best, dp[cur][r1 - 1][r2 - 1]); dp[nxt][r1][r2] best val; } } cur nxt; } cout dp[cur][m][m] endl;滾動(dòng)數(shù)組的核心是每層開始前必須把目標(biāo)層全部重置為負(fù)無(wú)窮。如果不重置上一層殘留的舊值會(huì)被新層讀到導(dǎo)致計(jì)算出不存在的路徑。這個(gè) bug 非常隱蔽肉眼看不出來(lái)只能靠造數(shù)據(jù)對(duì)比三維版和滾動(dòng)版結(jié)果才能發(fā)現(xiàn)。4.3 踩坑清單四個(gè)常見(jiàn)錯(cuò)誤我把實(shí)際寫代碼過(guò)程中踩過(guò)、以及幫別人排查過(guò)的幾個(gè)高頻 bug 列在這里。第一個(gè)是循環(huán)起點(diǎn)錯(cuò)。dp[2][1][1] 必須單獨(dú)初始化然后 for 循環(huán)從 s3 開始。如果把 s2 也放進(jìn)循環(huán)里又寫了 r1r2 時(shí) continue那么起點(diǎn)狀態(tài)會(huì)被直接跳過(guò)整個(gè) DP 從一開始就全是負(fù)無(wú)窮答案必然錯(cuò)。每當(dāng)你發(fā)現(xiàn)代碼輸出一個(gè)非常大的負(fù)數(shù)先檢查初始化。第二個(gè)是行范圍寫錯(cuò)。r 的范圍不是 1 到 m而是要滿足列坐標(biāo) s-r 落在 1 到 n 之間所以是 max(1, s-n) 到 min(m, s-1)。寫錯(cuò)范圍后要么越界訪問(wèn)要么把非法位置當(dāng)成合法位置計(jì)算答案會(huì)莫名偏大。第三個(gè)是終點(diǎn)的權(quán)值。終點(diǎn)是唯一允許 r1 r2 的普通同格狀態(tài)起點(diǎn)也允許但已經(jīng)單獨(dú)初始化了此時(shí) a[m][n] 必須只算一次。代碼里我用 if (r1 ! r2) val a[r2][c2] 來(lái)保證注意千萬(wàn)不要在終點(diǎn)加兩次。第四個(gè)是滾動(dòng)數(shù)組不清空。這個(gè)前面已經(jīng)提過(guò)目標(biāo)層必須 memset 回負(fù)無(wú)窮。另一個(gè)相關(guān)小問(wèn)題是負(fù)無(wú)窮的取值用 -0x3f3f3f3f 而不是 int 的最小值否則加一個(gè)正權(quán)值就可能溢出成奇怪的正數(shù)。4.4 驗(yàn)證思路寫完代碼后我一般不會(huì)只跑官方樣例就收工。傳紙條這種二維網(wǎng)格DP最怕的是判重邏輯在某個(gè)邊界偷偷失效。我的驗(yàn)證套路是先用暴力搜索枚舉所有合法路徑組合在小矩陣上跟 DP 結(jié)果對(duì)拍確認(rèn)無(wú)誤后再用隨機(jī)矩陣跑三維版和滾動(dòng)版對(duì)比兩者輸出是否完全一致。對(duì)拍腳本其實(shí)很簡(jiǎn)單暴力 DFS 在 m、n 不超過(guò) 6 的時(shí)候完全跑得動(dòng)。把 DP 答案和暴力答案逐一比較能一次性發(fā)現(xiàn)絕大多數(shù)狀態(tài)設(shè)計(jì)錯(cuò)誤。這個(gè)習(xí)慣幫我排過(guò)很多次“樣例過(guò)了但 WA”的冤案。5. 從傳紙條到方格取數(shù)雙狀態(tài)DP還能套在哪5.1 和方格取數(shù)只差一個(gè)判重很多人第一次接觸雙狀態(tài)DP是從方格取數(shù)那道經(jīng)典題開始的它和傳紙條是天然的姐妹題。方格取數(shù)的題意也是兩條從左上到右下的路徑但兩條路徑允許相交或重疊只是重疊格子里的數(shù)字只計(jì)一次。傳紙條則是直接禁止相交。兩題的代碼幾乎可以互相改傳紙條代碼里那行“r1 r2 且非終點(diǎn)就 continue”的邏輯在方格取數(shù)里變成“r1 r2 時(shí)只加一次權(quán)值但不跳過(guò)”。反過(guò)來(lái)方格取數(shù)代碼加上一行中間碰頭跳過(guò)就變成傳紙條。理解了這一點(diǎn)兩道題等于一起復(fù)習(xí)了。我用一個(gè)簡(jiǎn)單對(duì)比表記錄兩者的核心差異題目?jī)蓷l路徑能否共享中間格子判重處理方式DP思路傳紙條不能r1r2 且非終點(diǎn)時(shí)直接跳過(guò)同步三維DP方格取數(shù)可以但共享格只計(jì)一次r1r2 時(shí)權(quán)值只加一次同步三維DP5.2 障礙物、三人副本與不可壓縮場(chǎng)景如果題目在矩陣?yán)锛尤胝系K物比如某些格子不能走處理方式是把這些格子的權(quán)值設(shè)為負(fù)無(wú)窮并在轉(zhuǎn)移前判斷當(dāng)前位置是否合法。更嚴(yán)謹(jǐn)?shù)淖龇ㄊ菭顟B(tài)里根本不進(jìn)入這些格子直接把對(duì)應(yīng) dp 值留在負(fù)無(wú)窮。如果題目從兩個(gè)人升級(jí)成三個(gè)人傳紙條三條路徑需要同時(shí)規(guī)劃狀態(tài)就變成 dp[s][r1][r2][r3]四個(gè)維度行加列仍等于公共步數(shù) s。狀態(tài)數(shù)變成 O((mn) * m^3)在 m、n 較小的數(shù)據(jù)范圍下依然可行。判重邏輯也相應(yīng)擴(kuò)展成三個(gè)行坐標(biāo)兩兩不能相等。需要警惕的是雙狀態(tài)DP不是萬(wàn)能的。它的核心前提是“多個(gè)角色的移動(dòng)步數(shù)永遠(yuǎn)相同”。如果題目允許某個(gè)人在某一步停留或者路徑可以走回頭路那么行加列相等這個(gè)不變量就被破壞了必須回到更一般的高維狀態(tài)或者換成分層圖模型。判斷一道題能不能用“總步數(shù)若干坐標(biāo)”壓縮只需要看每個(gè)角色的每步移動(dòng)是否都嚴(yán)格消耗一個(gè)單位時(shí)間、且方向單調(diào)。我自己在實(shí)際做題中還有一個(gè)習(xí)慣拿到網(wǎng)格DP先不急著寫代碼先手寫算幾個(gè)小狀態(tài)確認(rèn)坐標(biāo)換算公式。傳紙條這道題最精彩的地方在于它把“同步時(shí)鐘”這個(gè)抽象概念落到了非常具體的網(wǎng)格上。一旦想通兩個(gè)人是在同一排秒針里移動(dòng)三維狀態(tài)、四路轉(zhuǎn)移、碰頭判重這些細(xì)節(jié)就全部變得順理成章。希望這篇梳理能幫你少走一點(diǎn)我當(dāng)時(shí)走過(guò)的彎路。