很多人學(xué)動態(tài)規(guī)劃第一輪啃概念覺得“最優(yōu)子結(jié)構(gòu)、無后效性、重疊子問題”說得頭頭是道合上書就廢。真正拿到一道新題狀態(tài)定義想一小時轉(zhuǎn)移方程憋不出來邊界條件一寫就錯。這篇《動態(tài)規(guī)劃理論基礎(chǔ)II》不打算再抄一遍教材而是想把理論和實(shí)操中間那層斷層補(bǔ)上狀態(tài)到底怎么定義、轉(zhuǎn)移方程怎么推、經(jīng)典模型怎么歸類、出了問題怎么調(diào)。適合的讀者是已經(jīng)大概知道DP是什么、但做題還經(jīng)?？さ娜恕Ｈ绻闶橇慊A(chǔ)建議先去把遞歸、記憶化搜索和斐波那契這類例子弄熟再回來看這篇。很多人以為DP難在轉(zhuǎn)移方程其實(shí)我刷了這么多題之后的感覺是90%的卡殼都出在狀態(tài)定義上。狀態(tài)是動態(tài)規(guī)劃的地基地基歪了后面全是空中樓閣。這篇我會用大量具體例子把我平時做題時的思考過程直接擺出來盡量不寫一句正確的廢話。1. 狀態(tài)設(shè)計(jì)動態(tài)規(guī)劃真正難住人的第一步1.1 狀態(tài)定義的本質(zhì)你在為子問題拍一張快照狀態(tài)到底是什么我的理解是狀態(tài)是你對某個子問題的一個“快照”它用幾個參數(shù)把解決這個問題所必須知道的信息濃縮起來結(jié)果值就是這個快照對應(yīng)的最優(yōu)答案。為什么要這么想因?yàn)閯討B(tài)規(guī)劃本質(zhì)上是對遞歸搜索的緩存只有參數(shù)完全相同的子問題才能共用緩存。所以狀態(tài)定義的第一原則是參數(shù)要包含“未來決策所需的全部信息”同時又盡量少帶無關(guān)信息。拿最長上升子序列來舉例。假設(shè)我想定義dp[i]表示“前i個元素的最長上升子序列長度”夠不夠不夠。原因是后面元素能不能接上取決于當(dāng)前子序列的末尾值是多少而“前綴的最長值”不一定是“尾巴最有機(jī)會接新元素”的那一個。比如數(shù)組是[2, 5, 3, 7, 4]只看前3個元素最長上升子序列是[2, 5]長度2以3結(jié)尾的子序列是[2, 3]長度也是2。但后面的4能接在3后面卻不能接在5后面。如果狀態(tài)里不記錄“以誰結(jié)尾”這個信息就丟了。所以更準(zhǔn)確的狀態(tài)是dp[i]以第i個元素結(jié)尾的最長上升子序列長度答案是對所有dp[i]取最大值。這個例子的價值在于它展示了一個思考模板每次寫狀態(tài)之前問自己一句“決策最后一步的時候我需要知道關(guān)于之前的哪些信息”。需要知道處理到哪個位置這是一個維度需要知道當(dāng)前結(jié)尾的值、剩余容量、已用次數(shù)這些是追加的維度。額外維度不是拍拍腦袋加上去的而是為了保證無后效性——所有會影響未來決策的信息都必須收進(jìn)狀態(tài)里。1.2 從題目條件反推狀態(tài)要有幾維我剛開始學(xué)DP的時候最喜歡猜狀態(tài)看到數(shù)字就寫dp[n]結(jié)果經(jīng)常把一維用到底。后來養(yǎng)成一個習(xí)慣先看輸入?yún)?shù)的數(shù)量。如果輸入只有一個序列狀態(tài)通常至少一維如果輸入里有一個容量、一個上限、一個次數(shù)約束你就要認(rèn)真考慮是不是該再加一維。因?yàn)闋顟B(tài)維度的本質(zhì)就是遞歸搜索樹上一個節(jié)點(diǎn)需要記錄哪些參數(shù)。舉個例子0-1背包問題N個物品每個物品有重量wi和價值vi背包容量W求能裝下的最大價值。搜索樹上一個節(jié)點(diǎn)需要知道兩件事當(dāng)前處理到第幾個物品了包里還剩多少容量。這就是二維狀態(tài)dp[i][j]表示前i個物品里選一些放進(jìn)容量j的包能拿到的最大價值。同樣的題目如果加一個限制“總共最多選K個物品”那必須再開一維變成dp[i][j][k]表示前i個物品、用了j容量、已經(jīng)挑了k個物品時的最大價值。規(guī)律很簡單多一個會被限制的條件通常就多一維狀態(tài)。不過也要提醒一句狀態(tài)維度不是越大越好。每多一維時間和空間可能就多一個數(shù)量級。真正見功夫的是信息壓縮題目里每個物品有編號但背包問題根本不需要知道選的是哪幾個只需要知道考慮了多少個、用了多少容量。把“具體集合”壓縮成“已考慮的個數(shù)”這就是從指數(shù)級搜索降到多項(xiàng)式DP的關(guān)鍵。2. 轉(zhuǎn)移方程是怎么一步一步推出來的2.1 永遠(yuǎn)先想“最后一步”是什么轉(zhuǎn)移方程不是靈光一現(xiàn)它描述的是當(dāng)前這個狀態(tài)可以從哪些前驅(qū)狀態(tài)通過一次決策到達(dá)。我自己的習(xí)慣是“以終為始”——不要從dp[1]開始想遞推到dp[n]而是反過來想假設(shè)當(dāng)前狀態(tài)已經(jīng)算好了它的值是從哪些來源拼出來的。一維爬樓梯是最簡單的示范。要到第n階最后一步只能是從n-1階邁一階或者從n-2階邁兩階。這兩個來源互斥且完備所以dp[n] dp[n-1] dp[n-2]。這個例子太簡單但思路通用。再看一個稍微有味道的題零錢兌換給定總額amount和硬幣面額數(shù)組coins求湊出這個總額最少需要幾枚硬幣。湊出x元最后一步必然是選擇一枚面額為c的硬幣那么前一個狀態(tài)就是“湊x-c元”。把所有c都枚舉一遍取最小得到dp[x] min(dp[x - c] for c in coins) 1這里的前驅(qū)不是固定的一個而是一組候選由最后一個決策決定。這正是轉(zhuǎn)移方程最常見的形態(tài)枚舉最后一步的所有可能從各個前驅(qū)狀態(tài)取最優(yōu)或求和。最長上升子序列也一樣。dp[i]表示以第i個元素結(jié)尾的LIS長度那么倒數(shù)第二個元素是某個下標(biāo)j必須滿足j i且nums[j] nums[i]。于是dp[i] max(1, max(dp[j] 1 for j in range(i) if nums[j] nums[i]))所有轉(zhuǎn)移方程本質(zhì)上都在做同一件事枚舉“從哪個狀態(tài)來”。你把這個邏輯想通了就不再需要背任何DP模板。2.2 邊界條件與循環(huán)順序兩個讓人頭大的細(xì)節(jié)邊界條件寫不對大概率是沒想清楚“空狀態(tài)”的含義。我的經(jīng)驗(yàn)是不要把所有dp都統(tǒng)一初始化成0必須先明確每個格子代表的是“合法狀態(tài)”還是“不可達(dá)狀態(tài)”。求最大值時不可達(dá)狀態(tài)常設(shè)成負(fù)無窮或-1求最小值時不可達(dá)狀態(tài)常設(shè)成正無窮只有真正可以當(dāng)作起點(diǎn)的狀態(tài)才單獨(dú)初始化成0、1或其他具體值。舉一個典型的反例。求最少跳躍次數(shù)到達(dá)數(shù)組末尾如果你把所有dp初始化為0轉(zhuǎn)移時做min操作那么所有狀態(tài)都會從0這個“假合法”狀態(tài)取到最小值答案永遠(yuǎn)是0。正確做法是把dp[0]初始化為0其余初始化為很大的數(shù)比如float(inf)然后當(dāng)某個狀態(tài)能從更少步數(shù)的合法狀態(tài)跳過來時才更新。這層理解比背“初始化為INF”更重要。循環(huán)順序也一樣。動態(tài)規(guī)劃本質(zhì)上是在一張有向無環(huán)圖上按拓?fù)湫蛱畋硪粋€狀態(tài)依賴誰就要保證在計(jì)算它之前被依賴的格子已經(jīng)被填好。爬樓梯從2到n正著循環(huán)因?yàn)閐p[i]依賴dp[i-1]和dp[i-2]有些倒推問題依賴dp[i1]那就要從n-1到0倒著循環(huán)。區(qū)間DP必須外層按區(qū)間長度枚舉因?yàn)殚L區(qū)間依賴短區(qū)間0-1背包必須容量倒序枚舉因?yàn)橐苊猱?dāng)前物品被重復(fù)使用。這些都不是需要死記的口訣而是“依賴先算好”的自然結(jié)果。3. 三大經(jīng)典模型背后的統(tǒng)一邏輯3.1 背包模型容量與價值之間的權(quán)衡背包問題之所以經(jīng)典是因?yàn)樗橄罅艘淮箢愘Y源分配問題手里有總量有限的資源一大堆候選項(xiàng)目各有代價和收益怎么選收益最大。0-1背包、完全背包、多重背包的區(qū)別本質(zhì)只是每個物品能用幾次。0-1背包的轉(zhuǎn)移很多人都會寫for i in range(1, n 1): for j in range(capacity, weight[i] - 1, -1): dp[j] max(dp[j], dp[j - weight[i]] value[i])這里dp[j]表示容量為j時能拿到的最大價值。為什么要倒序枚舉容量因?yàn)檎虻脑捘阌?jì)算dp[j]時讀到的dp[j - weight[i]]可能已經(jīng)被這一輪外層循環(huán)更新過了它已經(jīng)包含了“選入第i個物品”的結(jié)果于是同一輪里你能把同一個物品塞進(jìn)去兩次。倒序能保證讀到的永遠(yuǎn)是上一層的老值也就是說每件物品最多被選一次。完全背包和0-1背包的轉(zhuǎn)移幾乎一樣唯一的區(qū)別是內(nèi)層循環(huán)改成正序for j in range(weight[i], capacity 1): dp[j] max(dp[j], dp[j - weight[i]] value[i])用剛才的邏輯解釋就通了正序循環(huán)時dp[j - weight[i]]可能是剛剛被本輪更新過的新值它已經(jīng)包含了使用第i個物品的可能所以一個物品可以被反復(fù)使用正好符合“無限量供應(yīng)”的語義。你看根本不用背哪個背包正序哪個倒序把覆蓋順序想明白就行了。多重背包是另一個故事。每個物品最多用cnt次樸素做法是再加一層循環(huán)枚舉使用次數(shù)復(fù)雜度直接乘上一個k。經(jīng)驗(yàn)做法是二進(jìn)制拆分把cnt拆成1、2、4、8、……以及最后剩下的余數(shù)每一份都當(dāng)成一個獨(dú)立的新物品然后跑0-1背包。為什么可行因?yàn)槿魏?到cnt之間的整數(shù)都能由這些2的冪子集組合出來。這個辦法理解了以后競賽里處理多重背包就很順手。3.2 區(qū)間DP先合并小的再合并大的區(qū)間DP是另一類特別常見的模型狀態(tài)通常是dp[l][r]表示對區(qū)間[l, r]做某種處理后的最優(yōu)值。最經(jīng)典的例子是石子合并有一排石子堆每次只能合并相鄰兩堆代價是這兩堆重量之和問合并成一堆的最小總代價。關(guān)鍵在于最后一步整堆石頭一定是由左右兩部分合并來的所以轉(zhuǎn)移方程是枚舉分界點(diǎn)kdp[l][r] min(dp[l][k] dp[k 1][r] sum(l, r) for k in range(l, r))其中sum(l, r)是區(qū)間[l, r]的總重量是最后一次合并付出的代價。代碼結(jié)構(gòu)基本固定先枚舉區(qū)間長度len再枚舉左端點(diǎn)l算出右端點(diǎn)r l len - 1最后枚舉分界點(diǎn)k。三重循環(huán)復(fù)雜度O(n^3)。為什么外層必須枚舉長度因?yàn)閐p[l][r]依賴的所有子區(qū)間長度都小于len只有按長度從小到大才能保證需要的值都已經(jīng)算好。矩陣鏈乘問題也是同一個骨架dp[l][r]表示第l個到第r個矩陣連乘的最少乘法次數(shù)轉(zhuǎn)移里多了一個維度參數(shù)p代價是p[l-1] * p[k] * p[r]。很多看起來完全不同的題比如戳氣球、括號匹配、多邊形剖分最后都是這個模式。所以我建議你把區(qū)間DP的“長度-左端-分界點(diǎn)”三層循環(huán)寫成肌肉記憶在此基礎(chǔ)上理解每道題自己的代價函數(shù)是什么。3.3 狀態(tài)機(jī)DP把“當(dāng)前處于什么階段”寫進(jìn)狀態(tài)有些序列DP題除了位置維度之外還隱含一個“當(dāng)前處于什么狀態(tài)”的信息。最典型的就是打家劫舍一排房子不能偷相鄰的兩家問最大收益。如果只定義dp[i]表示前i家的最大金額你會發(fā)現(xiàn)轉(zhuǎn)移很別扭因?yàn)槟悴恢赖趇家到底偷沒偷也就不知道第i1家能不能偷。解決方案是加一維dp[i][0] max(dp[i-1][0], dp[i-1][1]) # 不偷第i家 dp[i][1] dp[i-1][0] nums[i] # 偷第i家0表示“第i家沒偷”1表示“第i家偷了”。這個狀態(tài)定義就是一個微型狀態(tài)機(jī)節(jié)點(diǎn)是0/1轉(zhuǎn)移邊是“從某個狀態(tài)走到另一個狀態(tài)”。股票買賣問題更好理解。每天結(jié)束時你手里要么持有股票要么不持有。dp[i][0]表示第i天結(jié)束時手上沒有股票的最大現(xiàn)金dp[i][1]表示第i天結(jié)束時持有股票的最大現(xiàn)金dp[i][0] max(dp[i-1][0], dp[i-1][1] price[i]) dp[i][1] max(dp[i-1][1], dp[i-1][0] - price[i])持有狀態(tài)可以繼續(xù)持有也可以賣掉變成不持有不持有狀態(tài)可以繼續(xù)觀望也可以買入變成持有。限制“最多交易k次”時再加一維k買入動作消耗一次交易次數(shù)。狀態(tài)機(jī)DP的價值在于把題目里用自然語言描述的限制顯式地變成狀態(tài)維度之后轉(zhuǎn)移就是單純地在狀態(tài)圖上走邊。這個思想再往前一步還能處理允許冷卻期、包含手續(xù)費(fèi)等一系列股票衍生題。4. 實(shí)戰(zhàn)前必看DP調(diào)試三板斧與常見錯誤速查4.1 先判斷能不能用DP三個必要條件很多人拿到題就開始寫狀態(tài)其實(shí)第一步應(yīng)該判斷這題適不適合DP。三個必要條件是最優(yōu)子結(jié)構(gòu)、重疊子問題、無后效性。最優(yōu)子結(jié)構(gòu)指原問題的最優(yōu)解可以由子問題的最優(yōu)解組裝出來重疊子問題指同一個子問題會被多個更大的問題反復(fù)使用無后效性指一旦某個狀態(tài)的值確定后面怎么決策都不受到達(dá)該狀態(tài)的具體路徑影響。用零錢兌換做例子很合適。硬幣面額1、5、11要湊15。如果貪心每次都拿最大的11得到的是4枚硬幣但最優(yōu)解是5553枚。為什么貪心失效因?yàn)榫植孔顑?yōu)推不出全局最優(yōu)。DP能行是因?yàn)椤皽?5的最少硬幣數(shù)”可以由“湊14、湊10、湊4”這三個子問題各加1枚得到子問題之間重疊且獨(dú)立。這三條都滿足DP就是合適的工具。如果問題有重疊子問題但不存在最優(yōu)子結(jié)構(gòu)那DP也未必成立。比如求最長簡單路徑路徑不能重復(fù)經(jīng)過節(jié)點(diǎn)子路徑的最優(yōu)選擇會互相影響這時候DP就失靈了。所以我的例行公事是拿到題目先自言自語兩句話——這個全局最優(yōu)能不能拆成子問題最優(yōu)后面決策還需要知道前面哪些破事如果都說得通再動筆寫狀態(tài)。4.2 調(diào)試DP三板斧第一板斧是打表。寫完轉(zhuǎn)移方程先輸出整個dp數(shù)組或dp矩陣逐行看。二維表就一張張打印看哪些格子是無窮大、哪個格子是起點(diǎn)、每個格子是從哪個格子轉(zhuǎn)移來的。很多時候你一眼就能看出“這個值是從一個不可能的狀態(tài)推來的”。第二板斧是造最小用例。n等于1、等于2、空數(shù)組、只有一堆石子這些邊界情況手算答案特別容易跑完程序一對比就知道邊界對不對。小數(shù)據(jù)錯了再用打表定位效率極高。第三板斧是暴力對拍。寫一個純遞歸或直接枚舉所有方案的暴力方法不關(guān)心復(fù)雜度然后生成幾十組n不超過8的小隨機(jī)數(shù)據(jù)把暴力結(jié)果和DP結(jié)果逐個比對。這個方法極其土但極其有效。我個人的習(xí)慣是每寫一個DP題只要不是考場趕時間都會順手寫個暴力對拍。一旦發(fā)現(xiàn)結(jié)果不一致打印DP表和暴力的搜索路徑幾乎沒有定位不了的問題。4.3 常見錯誤速查表錯誤現(xiàn)象常見原因檢查方向求最小值結(jié)果偏大不可達(dá)狀態(tài)沒有設(shè)成無窮大或者初始狀態(tài)沒設(shè)置檢查dp初值和dp[0]的語義求最大值結(jié)果偏小不可達(dá)狀態(tài)設(shè)成了0但0不是合法起點(diǎn)檢查負(fù)無窮或-1的設(shè)置答案總是差1下標(biāo)從0還是從1沒統(tǒng)一dp[0]含義沒想清逐個狀態(tài)重讀定義背包結(jié)果變成可以重復(fù)選0-1背包內(nèi)層循環(huán)寫成了正序回到“覆蓋順序”理解區(qū)間DP結(jié)果錯外層沒有按區(qū)間長度枚舉檢查計(jì)算順序是否是拓?fù)湫驖L動數(shù)組后結(jié)果變錯壓縮維度時覆蓋了后面還要用的舊值每次更新前確認(rèn)舊值是否已被消費(fèi)表格最后再補(bǔ)一句我的體會初值的本質(zhì)是“這個狀態(tài)下還沒做任何決策時的信息”。求方案數(shù)dp[0]常常等于1因?yàn)闇惓隹占挥幸环N方案求最少步數(shù)dp[0]常常等于0因?yàn)樵夭挥米卟豢蛇_(dá)狀態(tài)設(shè)成極大或極小是為了讓min/max操作自動避開它。想明白這些邊界條件就不是靠猜了。4.4 空間優(yōu)化不是炫技是必要的工程意識當(dāng)轉(zhuǎn)移只依賴上一層的狀態(tài)時可以把二維數(shù)組壓成兩個一維數(shù)組甚至一個數(shù)組。滾動數(shù)組最經(jīng)典的應(yīng)用就是背包空間優(yōu)化把dp[i][j]壓成dp[j]前提是循環(huán)方向正確保證更新時讀到的還是上一層的值。空間優(yōu)化后代碼看起來更簡潔但對“什么時候覆蓋舊值”的要求更高所以我建議初學(xué)者先寫二維版本驗(yàn)證正確后再壓維不要上來就寫滾動數(shù)組然后瘋狂debug。再往上走還有狀態(tài)壓縮DP用一個整數(shù)bitmask表示一個集合。比如旅行商問題dp[mask][v]表示已經(jīng)訪問過的城市集合為mask當(dāng)前停在v點(diǎn)的最小花費(fèi)。這類題的狀態(tài)本身就是集合維度拆不開只能用mask壓縮。這是理論基礎(chǔ)的延伸方向先知道有這個東西等真正遇到再把bitmask的幾個技巧撿起來?；氐介_頭的那個問題動態(tài)規(guī)劃的理論基礎(chǔ)到底在講什么我現(xiàn)在的答案是只講兩件事狀態(tài)里存什么狀態(tài)之間怎么走。狀態(tài)設(shè)計(jì)回答前者轉(zhuǎn)移方程和循環(huán)順序回答后者。這兩件事想明白了剩下的事情都可以靠調(diào)試和練習(xí)磨出來。最后分享一個小經(jīng)驗(yàn)也是我用了很久都覺得很有效的習(xí)慣拿到任何一道DP題先在草稿紙上寫三行注釋——狀態(tài)定義、轉(zhuǎn)移方程、初始條件然后才開始寫代碼。這個動作看著傻但它能逼著你在動手之前把所有邏輯漏洞想清楚。動態(tài)規(guī)劃不是靠靈感靠的是把每一步都想明白的耐心。