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