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