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