做動態(tài)規(guī)劃做到第八期回頭看看踩過的坑、總結(jié)過的套路確實值得單獨寫一篇復盤。這系列前七篇我分別講了狀態(tài)設計、轉(zhuǎn)移方程、記憶化搜索、數(shù)位DP、樹形DP、優(yōu)化技巧和經(jīng)典模型這次“動態(tài)規(guī)劃8”就換個角度不堆新模型而是把所有核心模型原理串起來重點拆線性DP和背包問題這兩條主線順便聊聊車輛動態(tài)規(guī)劃這類實際問題怎么用DP思想就當是階段性總結(jié)加實戰(zhàn)手冊。如果你是剛跟著題單刷到這里的同學或者刷了hot100但總在背包問題上卡殼這篇應該能幫上忙。很多人刷動態(tài)規(guī)劃總覺得“一看就會一寫就廢”問題往往不在代碼而在建模那一步。本篇就從模型原理切入把狀態(tài)、轉(zhuǎn)移、邊界、優(yōu)化一整個鏈路拉開配合洛谷題單和常見工程案例盡量讓你看完能直接照著寫。1. 動態(tài)規(guī)劃的核心模型與解題套路1.1 動態(tài)規(guī)劃到底在“規(guī)劃”什么動態(tài)規(guī)劃的本質(zhì)是對“狀態(tài)”做決策。我們用一組變量描述當前情況的所有關鍵信息這個描述就是狀態(tài)從當前情況做出下一步選擇后到達新情況這個過程就是轉(zhuǎn)移。整個問題因此變成一個多階段決策的最優(yōu)化問題。你吃東西點外賣就是個天然例子當前手里有預算和饑餓值是狀態(tài)每一道菜的價錢和熱量是決策吃完一份后預算減少、饑餓值下降是轉(zhuǎn)移目標是花最少的錢獲得最大滿足感就是目標函數(shù)。動態(tài)規(guī)劃要做的就是枚舉所有可能的“吃法組合”但用狀態(tài)復用避免重復計算。這引出一個關鍵認知只要狀態(tài)定義得足夠完整能夠覆蓋所有影響未來決策的信息那么把問題拆成子問題后最優(yōu)解一定可以通過最優(yōu)子結(jié)構(gòu)拼出來。這也是動態(tài)規(guī)劃有效的前提無后效性和最優(yōu)子結(jié)構(gòu)兩個概念說的其實是一件事當前決策只影響未來不影響過去的最優(yōu)結(jié)論。1.2 從狀態(tài)定義到轉(zhuǎn)移方程先解決“為什么”初學時我總急著寫轉(zhuǎn)移方程后來發(fā)現(xiàn)這是最效率最低的做法。正確順序是先回答四個問題問題里哪些量是可變的且會隨決策變化這些量里哪些會影響后續(xù)決策必須放進狀態(tài)當前這個狀態(tài)是從哪些前驅(qū)狀態(tài)轉(zhuǎn)移來的轉(zhuǎn)移時取了max還是min邊界值是什么比如線性DP里的經(jīng)典問題“最長上升子序列”核心變量是“當前位置”和“末尾元素大小”。我們定義dp[i]表示以第i個元素結(jié)尾的最長上升子序列長度遍歷所有j i當nums[j] nums[i]時嘗試更新dp[i] max(dp[i], dp[j] 1)。這里為什么把“以i結(jié)尾”而不是“前i個”作為狀態(tài)因為“以i結(jié)尾”保留了末尾元素這個關鍵信息后續(xù)能否拼接下一個更大元素完全取決于末尾值如果只定義“前i個的最長長度”就丟失了末尾大小沒法進行后續(xù)決策。這就是狀態(tài)設計的核心邏輯。再強調(diào)一點轉(zhuǎn)移方程不是“猜”出來的而是“從前驅(qū)狀態(tài)向后繼狀態(tài)推”推出來的。畫一張小圖把所有前驅(qū)狀態(tài)列出來方程自然就寫出來了。1.3 三類高頻DP模型對比把洛谷題單和LeetCode hot100翻一遍會發(fā)現(xiàn)高頻模型其實就幾類。這里重點梳理三類線性DP狀態(tài)維度是“位置”通常是dp[i]表示處理完前i個元素或到達第i個位置的最優(yōu)值。代表問題最大子段和、最長上升子序列、數(shù)字三角形、爬樓梯。區(qū)間DP狀態(tài)從“位置”變成“區(qū)間左右端點”dp[l][r]表示閉區(qū)間[l, r]上的最優(yōu)解轉(zhuǎn)移通常枚舉分割點k。代表問題石子合并、回文串分割、矩陣鏈乘。背包DP狀態(tài)是“決策約束的組合”dp[i][j]表示前i個物品在容量為j的背包中獲得的最大價值。它本質(zhì)是資源分配問題所有“有容量限制、有選擇成本”的題幾乎都能套背包。這三類不是互斥的線性DP中最長公共子序列也相當于雙序列線性DP背包也是線性枚舉的。把它們分開是為了快速定位模型實際做題時也可以綜合使用。建議每類各找十道題先把同一模型的題刷出感覺再混合訓練。2. 線性DP實戰(zhàn)拆解從數(shù)字三角形到雙序列2.1 數(shù)字三角形線性DP的“第一課”洛谷P1216數(shù)字三角形是一個極好的入門題。題目給出一個三角形從頂部出發(fā)每次可以向下或向右下走要求路徑上數(shù)字之和最大。很多人一上來就寫搜索其實這是典型的線性DP。定義dp[i][j]表示從頂部走到第i行第j列位置時所獲得的最大和。轉(zhuǎn)移方程dp[i][j] max(dp[i-1][j-1], dp[i-1][j]) a[i][j]從左上過來即上一行第j-1列從正上方過來即上一行第j列邊界是dp[1][1] a[1][1]其他無效位置用極小值初始化。這個轉(zhuǎn)移為什么可靠因為走到當前位置只有兩個方向前面每一步都已經(jīng)依賴子結(jié)構(gòu)被預處理出來了這就是線性DP“順著位置從左到右、從上到下”推進的典型形態(tài)。實現(xiàn)時候有兩點容易翻車一是二維數(shù)組越界建議把行、列坐標從1開始讀入把邊界多留一圈初始化成負無窮二是如果從上往下填表記得只枚舉當前行有效列范圍別把三角形外部的空格也當成0參與運算。2.2 最大子段和一維線性DP的狀態(tài)壓縮另一個很能說明問題的線性DP是最大子段和。給定一個數(shù)組求連續(xù)子數(shù)組的最大和。這道題最常見的O(n)寫法是pre max(pre nums[i], nums[i]) res max(res, pre)這里的pre說白了就是“以當前元素結(jié)尾的最大子段和”。很多人背下這段代碼卻不理解為什么pre要么累加要么重置。其實dp[i]表示以第i個元素結(jié)尾的最大子段和轉(zhuǎn)移只有兩種選擇把當前元素接到前一個子段后面dp[i] dp[i-1] nums[i]單獨成段dp[i] nums[i]取較大的那個就是pre max(pre nums[i], nums[i])。因為dp[i]只依賴dp[i-1]所以可以用一個變量滾動更新這就是空間優(yōu)化的雛形。這個例子還能很好解釋“狀態(tài)復用”計算dp[100]時dp[1]到dp[99]的最優(yōu)結(jié)論已經(jīng)在滾動中被重復利用不需要重新計算。2.3 雙序列線性DP最長公共子序列的轉(zhuǎn)移矩陣最長公共子序列LCS是雙序列線性DP的代表也是hot100和洛谷題單的?？汀６xdp[i][j]表示字符串A的前i個字符和B的前j個字符的最長公共子序列長度。轉(zhuǎn)移分情況如果A[i] B[j]那么dp[i][j] dp[i-1][j-1] 1否則dp[i][j] max(dp[i-1][j], dp[i][j-1])很多人不理解為什么不等時要取兩個方向的最大值。原因是如果當前兩個字符不相等那么現(xiàn)在的最長公共子序列要么來自“A去掉當前字符后和B的前j個”的結(jié)果要么來自“A的前i個和B去掉當前字符后”的結(jié)果這兩個候選都不一定是在同一個端點結(jié)束所以要取最大值。這個問題的轉(zhuǎn)移構(gòu)成了一個二維表格每一個格子只依賴左、上、左上三個方向。算完整個表后dp[n][m]就是答案。實際寫代碼時如果要用滾動數(shù)組要注意更新順序因為dp[i][j]依賴dp[i-1][j-1]一旦覆蓋當前行就可能丟失左上的舊值。通常用兩個臨時變量保存左上方和左邊的舊值或者干脆不加優(yōu)化先寫完整二維ac后再考慮空間優(yōu)化。這類雙序列問題的核心經(jīng)驗是把兩個序列的長度作為兩個維度寫進狀態(tài)狀態(tài)轉(zhuǎn)移就是“當前字符匹配/不匹配”的分支討論。凡是“兩個字符串/數(shù)組之間找關系”的題八成都可以嘗試雙序列DP。3. 背包問題模型01背包、完全背包與滾動數(shù)組3.1 01背包的狀態(tài)設計與轉(zhuǎn)移推導01背包是動態(tài)規(guī)劃里最經(jīng)典的模型之一。每件物品只有取或不取兩種選擇目標是背包容量有限時獲得最大總價值。洛谷題單里的采藥、開心的金明hot100里的分割等和子集底層都是01背包。先說標準定義有n個物品第i個物品重量為w[i]價值為v[i]背包總?cè)萘繛镃。定義dp[i][j]表示考慮前i個物品當前背包容量為j時能獲得的最大價值。轉(zhuǎn)移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) 當j w[i] dp[i][j] dp[i-1][j] 當j w[i]第一個max里dp[i-1][j]是不取第i個物品dp[i-1][j-w[i]] v[i]是取第i個物品先騰出w[i]的容量再放進去。這里為什么要用i-1狀態(tài)因為01背包要求每個物品只能選一次不能在同一輪里復用同一個物品所以必須參考上一輪的處理結(jié)果。圖示化思考整個dp表是一個n×C的矩陣i方向是物品順序j方向是容量。每個格子的值只由它上面一行同一列和左上方某個格子的值決定。方向明確代碼就好寫了。3.2 滾動數(shù)組優(yōu)化與遍歷順序的“禁忌”很多新手優(yōu)化背包空間把二維dp壓成一維dp[j]后發(fā)現(xiàn)結(jié)果莫名其妙變了。原因就出在遍歷順序上。一維優(yōu)化的標準寫法for i in 1..n: for j in C..w[i]: # 注意從大到小 dp[j] max(dp[j], dp[j-w[i]] v[i])為什么j要從大到小遍歷因為一維dp[j]在更新時dp[j-w[i]]必須仍然是“上一輪i-1”的結(jié)果而不能是當前輪已經(jīng)更新過的結(jié)果。如果j從小到大遍歷dp[j-w[i]]可能剛被本輪更新過相當于同一個物品被選了多次這就不再是01背包變成完全背包了。這是動態(tài)規(guī)劃題目里最經(jīng)典的“順序陷阱”沒有之一。我踩過這個坑兩次之后總結(jié)了一個記憶方法01背包是“從大到小偷著更新”完全背包是“從小到大正大光明更新”。把這個順口溜記下來背包題基本不會因為遍歷方向再出問題。3.3 完全背包與多重背包的差異完全背包表示每個物品可以無限取用轉(zhuǎn)移方程看似一樣只是dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])關鍵區(qū)別在于取第i個物品后剩余部分依然可以考慮再次取第i個物品所以依賴的是當前行dp[i][j-w[i]]而不是上一行dp[i-1][...]。用一維數(shù)組寫的時候j從小到大遍歷正好能利用本行已經(jīng)更新的值實現(xiàn)“無限復用”。多重背包則介于二者之間每個物品有數(shù)量限制count[i]。如果count很大可以二進制拆分把多個相同物品拆成1、2、4...份轉(zhuǎn)成01背包處理。這樣做的正確性在于任意數(shù)量都可以由這些二進制分組組合出來而拆出的每一組又只能取一次恰好符合01背包的約束。做題時首先要判斷每個物品可用的次數(shù)一次01、無限次完全包、有限次多重寶。這個判斷錯了遍歷順序也就跟著錯最后的dp表全亂。建議每次寫背包題前在注釋里寫清“類型遍歷方向”習慣養(yǎng)成就很少翻車。4. 從算法題到工程車輛動態(tài)規(guī)劃問題中的DP思想4.1 車輛調(diào)度為什么能抽象成DP算法題里的DP刷多了會發(fā)現(xiàn)真實工程中的很多問題也帶著DP的影子車輛動態(tài)規(guī)劃就是典型例子。這里說的“車輛動態(tài)規(guī)劃問題”不是某一個具體題目而是一大類資源調(diào)度優(yōu)化問題比如配送車輛路徑選擇、出租車調(diào)度、共享汽車投放本質(zhì)都是在容量、時間、里程等約束下對“車輛”這個資源做最優(yōu)分配。我們用一個簡化場景說明一輛車從起點出發(fā)要依次服務若干客戶點每個點有最早服務時間和最晚服務時間車輛有載重上限問最多能服務多少個點或者總行駛距離最短。這很像時間窗約束下的路徑問題完整解決需要組合優(yōu)化算法但可以考慮用DP處理其中一部分。比如假設路線順序已經(jīng)確定那么“當前到達某個點時剩余多少時間、還能接多少貨”就可以作為狀態(tài)做容量限制下的收益最大化這就是一個帶時間約束的背包。更常見的是“車輛數(shù)目運輸任務分配”問題多輛車分別裝載不同貨物每輛車容量有限希望總成本最小這種分配問題可以直接建模成多維背包每件貨物選或不選每輛車對應一個容量維度。4.2 用多維背包模擬車輛裝載問題假設有三輛車容量分別是C1、C2、C3有n件貨物每件重量w[i]、運送價值v[i]每件貨物必須由某一輛車運輸且每輛車的總重量不能超載目標是最大化總運送價值。這就是一個三維背包dp[a][b][c]表示三輛車分別已用容量a、b、c時的最大價值。每件貨物依次決策分別嘗試放入第一輛、第二輛、第三輛或者不放。轉(zhuǎn)移dp[a][b][c] max(dp[a][b][c], dp[a-w[i]][b][c] v[i] if aw[i], dp[a][b-w[i]][c] v[i] if bw[i], dp[a][b][c-w[i]] v[i] if cw[i])用滾動數(shù)組寫的時候三個維度都要從大到小遍歷原理和01背包一維優(yōu)化完全一樣保證每件貨物只被考慮一次。實際工程里維度可能更多比如還要加時間窗、冷熱鏈、司機休息時間維度一多DP表會指數(shù)膨脹這時就需要換成啟發(fā)式算法或列生成。不過這不代表DP思想沒有用恰恰相反很多啟發(fā)式算法在局部優(yōu)化階段還是會用DP做“容量分配”的子模塊所以算法題里練好的背包模型在工程項目里是能直接遷移的基礎能力。4.3 DP落地的工程注意事項真實車輛動態(tài)規(guī)劃問題和刷題有幾個明顯差別值得特別提醒維度爆炸動態(tài)規(guī)劃表的大小隨著狀態(tài)維度指數(shù)增長三輛車可能還勉強十輛車就沒法直接開三維數(shù)組了。工程上要么壓縮狀態(tài)要么放棄精確DP用近似方法。邊界條件復雜車輛路徑問題里“容量”“時間窗”“服務時間”相互耦合狀態(tài)必須定義得更細否則漏掉約束會導致結(jié)果不可用。性能要求線上系統(tǒng)往往要求毫秒級響應DP如果規(guī)模太大需要配合剪枝、預處理和空間壓縮。我見過一個團隊直接把算法競賽的二維背包代碼搬上生產(chǎn)環(huán)境結(jié)果輸入一變成百輛車就內(nèi)存爆掉。后來他們用貪心先排一個初始解再用DP只優(yōu)化幾個關鍵環(huán)節(jié)才把效果和性能都平衡下來。這個經(jīng)驗很重要工程里DP是解決問題的工具之一不是非要滿狀態(tài)求解才算用DP。5. hot100視角動態(tài)規(guī)劃高頻題與常見錯誤自查5.1 高頻DP題型的模型映射把LeetCode hot100里和DP相關的題目過一遍會發(fā)現(xiàn)它們絕大多數(shù)能歸入前文提到的模型。這里做一張映射表供自查題目類型核心模型狀態(tài)定義爬樓梯線性遞推dp[i]表示到達第i階的方法數(shù)最大子序和線性DPdp[i]表示以i結(jié)尾的最大子段和打家劫舍線性DPdp[i]表示前i間房能偷到的最大值最長遞增子序列線性DPdp[i]表示以i結(jié)尾的LIS長度分割等和子集01背包dp[j]表示是否能用元素湊出和j零錢兌換完全背包dp[j]表示湊出金額j的最少硬幣數(shù)編輯距離雙序列DPdp[i][j]表示A前i個字符到B前j個字符的編輯距離看到題目先對號入座能少走很多彎路。很多人喜歡直接憑感覺寫寫到一半發(fā)現(xiàn)狀態(tài)不全推倒重來其實花一分鐘先想清楚模型后面反而快很多。5.2 初始化與邊界最容易翻車的地方刷了這么多題我總結(jié)的DP錯誤里初始化錯誤占比遠超轉(zhuǎn)移方程錯誤。常見問題包括求最大值卻把dp數(shù)組初始化為0導致負權路徑被錯誤忽略。正確做法是針對求解目標求最大值時非法狀態(tài)用負無窮如-1e9求最小值時用正無窮如1e9。邊界漏算。比如dp[0]到底代表“空集合”還是“第一個元素”這個問題必須想清楚。像分割等和子集dp[0]要置為true表示空集能湊出0其他置為false。字符串數(shù)組從0還是從1開始。如果從0讀入轉(zhuǎn)移時dp[i-1]可能出現(xiàn)負數(shù)下標建議統(tǒng)一把數(shù)據(jù)下標后退一位dp數(shù)組多開一位。我自己每次寫完DP都會做三個邊界測試空輸入、最小規(guī)模、最大規(guī)模。比如n1時答案是什么C0或者容量為0時dp表變化是否符合預期這些測試雖然簡單卻經(jīng)常能揪出初始化問題。5.3 調(diào)試DP的實用手段打表與對比調(diào)試DP最有效的辦法不是單步跟蹤而是把dp表完整打出來逐行檢查是否合理。我通常會在關鍵轉(zhuǎn)移后加一段臨時輸出for i in range(1, n1): for j in range(1, C1): print(dp[i][j], end ) print()然后拿一個非常小的樣例手工推算一遍DP表把推出來的表格和程序輸出對比。只要某個格子對不上就順著它背后的轉(zhuǎn)移鏈往回找問題基本都能定位。這條方法雖然土但比任何調(diào)試器都好用。另一個技巧是寫一個暴力解法的對拍器DP寫完后用隨機數(shù)據(jù)讓兩組代碼同時跑結(jié)果不一致就不斷縮小數(shù)據(jù)規(guī)模。我在刷hot100時經(jīng)常這么干特別是轉(zhuǎn)移方向容易混的背包題對拍能節(jié)省大量手動驗算時間。5.4 動態(tài)規(guī)劃學習路徑的建議八期內(nèi)容走到這里如果還想繼續(xù)往前推進我給一條實操路徑。第一把線性DP和背包徹底吃透。這兩塊像動態(tài)規(guī)劃的地基把狀態(tài)設計、滾動數(shù)組、初始化這些基本功練熟其他模型都是延展。第二順著洛谷題單刷題每一道題都要能說出三個東西狀態(tài)定義、轉(zhuǎn)移方程、邊界條件。不能說出這三樣說明這道題還沒真正掌握哪怕AC了也是背模板。第三利用hot100查漏補缺。hot100里的DP題相比洛谷更偏工程思維題目描述更接近真實問題場景能把模型從競賽轉(zhuǎn)換為落地很有價值。第四學有余力再拓展區(qū)間DP、狀態(tài)壓縮DP、樹形DP。前七期內(nèi)容已經(jīng)把樹形DP和數(shù)位DP鋪墊過了這一期主要是把公共主線串一遍后面可以針對薄弱模型再各寫專題。我自己到現(xiàn)在寫DP依然會在草稿紙上先寫清“dp[i][j]代表什么”再動代碼。這一步看起來多花三分鐘但能防止后面半小時的無效調(diào)試。狀態(tài)定義清晰轉(zhuǎn)移方程基本是水到渠成的事。最后分享一個小經(jīng)驗遇到一個新問題先別急著套模型試試把題目改成“有一組選項、每個選項消耗資源且?guī)硎找?、總資源有限”的描述如果改得順多半就是背包改成“從前往后依次處理每個位置當前狀態(tài)只依賴前幾個位置”多半就是線性DP。這套判斷思路在車輛動態(tài)規(guī)劃和hot100里都幫我快速定過方向。希望這一篇也能讓你在DP這條路上少踩幾個坑多幾分確定性。