1. 為什么我要從零寫一套動(dòng)態(tài)規(guī)劃拆解動(dòng)態(tài)規(guī)劃這四個(gè)字幾乎是每個(gè)學(xué)算法的人繞不過去的一道坎。我見過太多人在面試前突擊背幾道背包問題、最長(zhǎng)公共子序列的模板結(jié)果題目稍微換個(gè)皮就完全沒思路。也見過有人刷了兩百道DP題遇到新題還是只能干瞪眼。問題出在哪不是題刷得不夠多而是從一開始就沒有建立起對(duì)動(dòng)態(tài)規(guī)劃這門“手藝”的正確認(rèn)知。我自己當(dāng)年學(xué)DP也走過彎路。最早接觸的是斐波那契數(shù)列的遞推寫法覺得不過如此后來碰到零錢兌換、編輯距離開始覺得有點(diǎn)意思再往后遇到狀態(tài)壓縮、區(qū)間DP、樹形DP整個(gè)人就懵了。真正讓我開竅的不是又刷了多少題而是有一天我突然想明白了一件事動(dòng)態(tài)規(guī)劃本質(zhì)上不是一種算法而是一種思考問題的方式——它教你怎么把一個(gè)大麻煩拆成一串小麻煩然后從小麻煩的答案里拼出大麻煩的答案。這套拆解我打算分幾篇來寫這是第一篇重點(diǎn)解決三個(gè)問題動(dòng)態(tài)規(guī)劃到底在干什么、怎么判斷一道題能不能用DP、以及最核心的——狀態(tài)和轉(zhuǎn)移方程到底怎么設(shè)計(jì)。我不會(huì)一上來就甩一堆數(shù)學(xué)公式而是用最直白的話和大量例子把每個(gè)概念揉碎了講。適合誰看如果你正在學(xué)算法、準(zhǔn)備面試、或者單純想搞明白這個(gè)被說爛了卻總也學(xué)不透的東西那這篇內(nèi)容就是寫給你的。哪怕你之前完全沒接觸過DP只要會(huì)寫最基本的循環(huán)和遞歸就能跟上。2. 動(dòng)態(tài)規(guī)劃到底在解決什么問題2.1 從一個(gè)最樸素的例子說起假設(shè)你要爬一個(gè)n級(jí)的樓梯每次只能走1級(jí)或者2級(jí)問一共有多少種走法。這個(gè)問題太經(jīng)典了經(jīng)典到很多人一看到就知道答案是斐波那契數(shù)列。但我想讓你關(guān)注的是思考過程而不是答案本身。當(dāng)你站在第n級(jí)臺(tái)階上往回看你最后一步是怎么上來的要么是從第n-1級(jí)走1級(jí)上來的要么是從第n-2級(jí)走2級(jí)上來的。沒有第三種可能。所以走到第n級(jí)的走法總數(shù)就等于走到第n-1級(jí)的走法數(shù)加上走到第n-2級(jí)的走法數(shù)。寫成式子就是f(n) f(n-1) f(n-2)。這個(gè)式子就是所謂的“狀態(tài)轉(zhuǎn)移方程”。而f(n)就是“狀態(tài)”它表示走到第n級(jí)臺(tái)階的走法總數(shù)。你看動(dòng)態(tài)規(guī)劃的核心思想在這里已經(jīng)體現(xiàn)得淋漓盡致了當(dāng)前問題的答案可以由若干個(gè)更小規(guī)模的同類問題的答案推導(dǎo)出來。那為什么不能直接用遞歸算因?yàn)檫f歸會(huì)把同一個(gè)子問題重復(fù)計(jì)算無數(shù)次。算f(5)需要f(4)和f(3)算f(4)又需要f(3)和f(2)f(3)被算了兩次。n稍微大一點(diǎn)計(jì)算量就爆炸了。動(dòng)態(tài)規(guī)劃的解決辦法就是把每個(gè)子問題的答案記下來用的時(shí)候直接查表不重復(fù)算。這就是“記憶化”或者“填表”的思想。2.2 動(dòng)態(tài)規(guī)劃與分治、貪心的本質(zhì)區(qū)別很多人分不清動(dòng)態(tài)規(guī)劃、分治法、貪心算法。它們確實(shí)有相似之處都是把大問題拆成小問題但拆的方式和合并的方式完全不同。分治法是把問題拆成若干個(gè)互不重疊的子問題分別求解后再合并。比如歸并排序左半邊和右半邊完全獨(dú)立排好之后一合并就完事。子問題之間沒有交集所以不需要記錄中間結(jié)果。貪心算法是每一步都選當(dāng)前看起來最優(yōu)的期望最終得到全局最優(yōu)。它不管子問題之間有沒有重疊也不回頭檢查之前的選擇。貪心能用的前提是問題具有“貪心選擇性質(zhì)”這個(gè)條件其實(shí)很苛刻大部分問題不滿足。動(dòng)態(tài)規(guī)劃則專門對(duì)付子問題重疊的情況。它承認(rèn)子問題會(huì)被反復(fù)用到所以老老實(shí)實(shí)把每個(gè)子問題的解存起來。同時(shí)它也不像貪心那樣只顧眼前而是通過狀態(tài)轉(zhuǎn)移方程把所有的可能性都考慮進(jìn)去最終選出最優(yōu)的那個(gè)。你可以這么理解分治是各干各的然后拼起來貪心是一條路走到黑動(dòng)態(tài)規(guī)劃是做好筆記、步步為營(yíng)。2.3 最優(yōu)子結(jié)構(gòu)與重疊子問題動(dòng)態(tài)規(guī)劃能用的前提是兩個(gè)性質(zhì)最優(yōu)子結(jié)構(gòu)和重疊子問題。最優(yōu)子結(jié)構(gòu)的意思是大問題的最優(yōu)解一定包含了子問題的最優(yōu)解。拿最短路徑來說如果從A到C的最短路徑經(jīng)過B那么A到B的那段一定也是最短的B到C的那段也一定是最短的。如果不是你換一條更短的整體不就更短了嗎這就矛盾了。所以只要問題具有最優(yōu)子結(jié)構(gòu)我們就可以放心地從子問題的最優(yōu)解推導(dǎo)大問題的最優(yōu)解。重疊子問題的意思是在遞歸求解的過程中同一個(gè)子問題會(huì)被多次遇到。爬樓梯那個(gè)例子就是典型f(3)在算f(5)和f(4)時(shí)都被用到了。如果子問題不重疊那用分治就好了沒必要上DP。這兩個(gè)性質(zhì)缺一不可。沒有最優(yōu)子結(jié)構(gòu)你從子問題推不出大問題沒有重疊子問題你記錄中間結(jié)果也沒意義白白浪費(fèi)空間。注意很多人誤以為“最優(yōu)子結(jié)構(gòu)”就是“局部最優(yōu)能推出全局最優(yōu)”這其實(shí)是貪心的思路。最優(yōu)子結(jié)構(gòu)說的是大問題的最優(yōu)解里面包含了子問題的最優(yōu)解但不代表你每一步都選局部最優(yōu)就能得到全局最優(yōu)。這個(gè)區(qū)別一定要想清楚。3. 狀態(tài)設(shè)計(jì)動(dòng)態(tài)規(guī)劃最核心也最難的一步3.1 狀態(tài)到底是什么如果把動(dòng)態(tài)規(guī)劃比作蓋房子那狀態(tài)就是磚塊轉(zhuǎn)移方程就是水泥。沒有磚塊水泥再多也砌不成墻。狀態(tài)設(shè)計(jì)對(duì)了轉(zhuǎn)移方程往往水到渠成狀態(tài)設(shè)計(jì)錯(cuò)了怎么推都推不出來。那狀態(tài)到底是什么簡(jiǎn)單說狀態(tài)就是你對(duì)當(dāng)前局面的一個(gè)完整描述。它必須包含足夠的信息使得從這個(gè)狀態(tài)出發(fā)你能做出下一步的決策并且能判斷這個(gè)狀態(tài)的好壞。同時(shí)狀態(tài)又不能包含多余的信息否則狀態(tài)空間會(huì)爆炸。拿爬樓梯來說狀態(tài)就是“當(dāng)前在第幾級(jí)臺(tái)階”。這個(gè)信息足夠了因?yàn)閺牡趇級(jí)臺(tái)階出發(fā)你只需要知道i是多少就能決定下一步走到i1還是i2。至于你之前是怎么走到第i級(jí)的走了多少步用了什么姿勢(shì)統(tǒng)統(tǒng)不重要。這就是狀態(tài)的“無后效性”——當(dāng)前狀態(tài)一旦確定后續(xù)的決策只依賴于當(dāng)前狀態(tài)與到達(dá)這個(gè)狀態(tài)的路徑無關(guān)。3.2 一維狀態(tài)與多維狀態(tài)的取舍狀態(tài)可以是多維的。爬樓梯是一維狀態(tài)因?yàn)橹恍枰粋€(gè)變量就能描述局面。但很多問題一個(gè)變量不夠用。比如經(jīng)典的“零錢兌換”給你若干種面額的硬幣問湊出金額n最少需要幾枚硬幣。這里狀態(tài)是“當(dāng)前需要湊出的金額”還是一維的。但如果加一個(gè)限制條件比如每種硬幣最多只能用一次那狀態(tài)就變成二維了dp[i][j]表示用前i種硬幣湊出金額j的最少硬幣數(shù)。因?yàn)槟阈枰馈艾F(xiàn)在考慮到第幾種硬幣了”和“還需要湊多少錢”這兩個(gè)信息。再比如“最長(zhǎng)公共子序列”兩個(gè)字符串狀態(tài)自然是二維的dp[i][j]表示第一個(gè)字符串的前i個(gè)字符和第二個(gè)字符串的前j個(gè)字符的最長(zhǎng)公共子序列長(zhǎng)度。因?yàn)槟阈枰瑫r(shí)知道兩個(gè)字符串各自處理到哪了。那什么時(shí)候該加維度判斷標(biāo)準(zhǔn)很簡(jiǎn)單如果你發(fā)現(xiàn)當(dāng)前狀態(tài)不足以做出下一步?jīng)Q策或者不足以判斷當(dāng)前局面的優(yōu)劣那就說明缺信息需要加維度。但每加一維狀態(tài)空間就乘一個(gè)量級(jí)時(shí)間和空間復(fù)雜度都會(huì)上去。所以要在“信息足夠”和“空間可控”之間找平衡。3.3 狀態(tài)的無后效性為什么重要無后效性是狀態(tài)設(shè)計(jì)的一條鐵律。它的意思是一旦當(dāng)前狀態(tài)確定了未來只與當(dāng)前狀態(tài)有關(guān)與怎么到達(dá)當(dāng)前狀態(tài)的歷史路徑無關(guān)。為什么這條這么重要因?yàn)槿绻磥硪蕾囉跉v史路徑那你的狀態(tài)就必須把歷史路徑也編碼進(jìn)去狀態(tài)空間會(huì)變得無比巨大動(dòng)態(tài)規(guī)劃就退化成暴力搜索了。舉個(gè)例子。假設(shè)你在玩一個(gè)游戲角色有生命值和魔法值兩個(gè)屬性。如果你設(shè)計(jì)的狀態(tài)是“當(dāng)前生命值和魔法值”那沒問題因?yàn)橄乱徊侥茏鍪裁粗蝗Q于當(dāng)前的血量和藍(lán)量。但如果你設(shè)計(jì)的狀態(tài)是“當(dāng)前生命值、魔法值、以及之前每一步的選擇”那就完蛋了狀態(tài)多到?jīng)]法存。所以設(shè)計(jì)狀態(tài)的時(shí)候一定要問自己我記錄的信息是否足以唯一確定后續(xù)的決策如果兩個(gè)不同的歷史路徑到達(dá)了同一個(gè)狀態(tài)它們后續(xù)的最優(yōu)決策是否相同如果相同說明狀態(tài)設(shè)計(jì)是合理的如果不同說明狀態(tài)里缺了關(guān)鍵信息需要補(bǔ)上。實(shí)操心得我剛開始學(xué)DP的時(shí)候經(jīng)常犯一個(gè)錯(cuò)誤——狀態(tài)里塞了太多沒用的信息。比如做背包問題非要把“當(dāng)前背包里裝了哪些物品”也記下來。其實(shí)完全沒必要因?yàn)楸嘲鼏栴}只關(guān)心“當(dāng)前容量還剩多少”和“當(dāng)前考慮到第幾個(gè)物品了”具體裝了哪些物品不影響后續(xù)決策。狀態(tài)越精簡(jiǎn)效率越高。4. 轉(zhuǎn)移方程從狀態(tài)到狀態(tài)的橋梁4.1 轉(zhuǎn)移方程的本質(zhì)是決策枚舉狀態(tài)設(shè)計(jì)好了接下來就是轉(zhuǎn)移方程。轉(zhuǎn)移方程說白了就是在當(dāng)前狀態(tài)下你有哪些選擇每個(gè)選擇會(huì)導(dǎo)致什么后果哪個(gè)后果最好用數(shù)學(xué)語言說轉(zhuǎn)移方程就是dp[state] opt{ dp[prev_state] cost }其中opt是最優(yōu)化操作取最大、最小、求和等prev_state是做出某個(gè)決策后到達(dá)的前一個(gè)狀態(tài)cost是這個(gè)決策的代價(jià)。還是拿爬樓梯舉例。狀態(tài)dp[i]表示走到第i級(jí)的走法數(shù)。在當(dāng)前狀態(tài)i下你只能從i-1或i-2走過來。所以dp[i] dp[i-1] dp[i-2]。這里的“決策”就是“最后一步是走1級(jí)還是走2級(jí)”兩種決策對(duì)應(yīng)的前一個(gè)狀態(tài)分別是i-1和i-2代價(jià)都是1種走法所以加起來。再拿零錢兌換舉例。狀態(tài)dp[j]表示湊出金額j所需的最少硬幣數(shù)。在當(dāng)前狀態(tài)j下你可以選擇任何一種面額的硬幣coin。如果選了coin那你就從狀態(tài)j-coin轉(zhuǎn)移過來代價(jià)是1枚硬幣。所以dp[j] min{ dp[j-coin] 1 }對(duì)所有滿足coin j的硬幣面額取最小值。你看轉(zhuǎn)移方程的核心就是枚舉所有可能的決策然后從中選出最優(yōu)的。枚舉的范圍取決于問題本身但思路是通用的。4.2 邊界條件別讓程序在起點(diǎn)就翻車轉(zhuǎn)移方程描述了狀態(tài)之間怎么跳但總得有個(gè)起點(diǎn)。邊界條件就是那些不需要轉(zhuǎn)移、可以直接給出答案的狀態(tài)。爬樓梯的邊界是dp[0] 1站在地面不動(dòng)就是一種走法和dp[1] 1走到第1級(jí)只有一種走法。零錢兌換的邊界是dp[0] 0湊出金額0不需要任何硬幣。最長(zhǎng)公共子序列的邊界是dp[0][j] 0和dp[i][0] 0任意字符串和空串的公共子序列長(zhǎng)度都是0。邊界條件看起來簡(jiǎn)單但實(shí)際寫代碼的時(shí)候特別容易出錯(cuò)。我見過太多人轉(zhuǎn)移方程推得漂漂亮亮結(jié)果邊界寫錯(cuò)了整個(gè)答案全盤皆輸。比如爬樓梯如果dp[0]設(shè)成0那dp[2] dp[1] dp[0] 1 0 1但實(shí)際應(yīng)該是2走兩次1級(jí)或者一次走2級(jí)。一個(gè)邊界錯(cuò)誤后面全錯(cuò)。注意邊界條件一定要根據(jù)問題的實(shí)際語義來確定不能憑感覺。建議在草稿紙上手動(dòng)算幾個(gè)小規(guī)模的情況驗(yàn)證邊界值是否正確。比如爬樓梯手動(dòng)算一下n0,1,2,3的情況看看邊界設(shè)成多少才能讓結(jié)果對(duì)得上。4.3 從遞歸到遞推兩種實(shí)現(xiàn)路徑有了狀態(tài)和轉(zhuǎn)移方程實(shí)現(xiàn)方式有兩種遞歸加記憶化和遞推填表。遞歸加記憶化的寫法更貼近轉(zhuǎn)移方程的數(shù)學(xué)形式代碼通常更簡(jiǎn)潔也更容易理解。思路是寫一個(gè)遞歸函數(shù)solve(state)先查表看這個(gè)狀態(tài)有沒有算過算過就直接返回沒算過就按照轉(zhuǎn)移方程遞歸計(jì)算算完存表再返回。這種寫法也叫“自頂向下”。遞推填表的寫法是先確定狀態(tài)的遍歷順序然后從邊界條件開始一層一層往外推直到算出目標(biāo)狀態(tài)。這種寫法也叫“自底向上”。它的好處是沒有遞歸棧開銷速度通常更快而且方便做空間優(yōu)化。兩種寫法各有優(yōu)劣。遞歸加記憶化寫起來快不容易搞錯(cuò)遍歷順序但遞歸深度太大會(huì)爆棧。遞推填表效率高但需要想清楚遍歷順序順序錯(cuò)了結(jié)果就錯(cuò)了。我的建議是初學(xué)的時(shí)候先用遞歸加記憶化因?yàn)樗慕Y(jié)構(gòu)和轉(zhuǎn)移方程幾乎一一對(duì)應(yīng)不容易出錯(cuò)。等熟練了再改成遞推填表追求更高的效率。下面用爬樓梯舉例兩種寫法都給你。遞歸加記憶化def climb(n, memo{}): if n 1: return 1 if n in memo: return memo[n] memo[n] climb(n-1, memo) climb(n-2, memo) return memo[n]遞推填表def climb(n): if n 1: return 1 dp [0] * (n 1) dp[0] 1 dp[1] 1 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]你看遞推版本里那個(gè)for循環(huán)的順序就是從前往后因?yàn)閐p[i]依賴于dp[i-1]和dp[i-2]所以必須先把小的算出來。如果依賴關(guān)系反過來遍歷順序就要反過來。這就是為什么遞推填表需要想清楚遍歷順序。5. 實(shí)戰(zhàn)拆解從題目到代碼的完整流程5.1 案例一最大子數(shù)組和題目給一個(gè)整數(shù)數(shù)組找出一個(gè)連續(xù)子數(shù)組使得它的和最大返回這個(gè)最大和。第一步設(shè)計(jì)狀態(tài)。最直接的想法是dp[i]表示“以第i個(gè)元素結(jié)尾的最大子數(shù)組和”。為什么強(qiáng)調(diào)“以第i個(gè)元素結(jié)尾”因?yàn)樽訑?shù)組必須是連續(xù)的如果dp[i]表示“前i個(gè)元素中的最大子數(shù)組和”那轉(zhuǎn)移的時(shí)候你沒法判斷第i個(gè)元素要不要接在前面的子數(shù)組后面。而“以第i個(gè)元素結(jié)尾”這個(gè)定義天然保證了連續(xù)性。第二步推轉(zhuǎn)移方程。對(duì)于dp[i]第i個(gè)元素有兩種選擇要么接在前面的子數(shù)組后面要么自己?jiǎn)为?dú)成為一個(gè)子數(shù)組。如果接在后面那和就是dp[i-1] nums[i]如果單獨(dú)和就是nums[i]。我們要最大的所以dp[i] max(dp[i-1] nums[i], nums[i])。第三步確定邊界。dp[0] nums[0]因?yàn)榈谝粋€(gè)元素結(jié)尾的子數(shù)組只有它自己。第四步確定答案。答案不是dp[n-1]而是max(dp[0], dp[1], ..., dp[n-1])因?yàn)樽畲笞訑?shù)組不一定以最后一個(gè)元素結(jié)尾。代碼實(shí)現(xiàn)def max_subarray(nums): n len(nums) dp [0] * n dp[0] nums[0] ans dp[0] for i in range(1, n): dp[i] max(dp[i-1] nums[i], nums[i]) ans max(ans, dp[i]) return ans這個(gè)題還可以做空間優(yōu)化因?yàn)閐p[i]只依賴于dp[i-1]所以用一個(gè)變量滾動(dòng)更新就行不需要整個(gè)數(shù)組。優(yōu)化后空間復(fù)雜度從O(n)降到O(1)。def max_subarray_optimized(nums): cur nums[0] ans nums[0] for i in range(1, len(nums)): cur max(cur nums[i], nums[i]) ans max(ans, cur) return ans實(shí)操心得空間優(yōu)化是動(dòng)態(tài)規(guī)劃進(jìn)階的必修課。很多DP問題的狀態(tài)轉(zhuǎn)移只依賴于前一層或前幾個(gè)狀態(tài)這時(shí)候就可以用滾動(dòng)數(shù)組或者變量來壓縮空間。但要注意空間優(yōu)化之后代碼的可讀性會(huì)下降如果是在面試中建議先寫未優(yōu)化的版本確認(rèn)邏輯正確后再提優(yōu)化思路。5.2 案例二最長(zhǎng)遞增子序列題目給一個(gè)整數(shù)數(shù)組找出最長(zhǎng)遞增子序列的長(zhǎng)度。子序列不要求連續(xù)但要求保持相對(duì)順序。第一步設(shè)計(jì)狀態(tài)。dp[i]表示“以第i個(gè)元素結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度”。同樣強(qiáng)調(diào)“以第i個(gè)元素結(jié)尾”理由和上面一樣。第二步推轉(zhuǎn)移方程。對(duì)于dp[i]我們需要往前看所有j i且nums[j] nums[i]的位置。如果nums[i]能接在nums[j]后面那長(zhǎng)度就是dp[j] 1。我們要最長(zhǎng)的所以dp[i] max(dp[j] 1)對(duì)所有滿足j i且nums[j] nums[i]的j。第三步邊界。每個(gè)元素至少可以自己構(gòu)成一個(gè)長(zhǎng)度為1的遞增子序列所以dp[i]初始值都是1。第四步答案。max(dp[0], ..., dp[n-1])。代碼實(shí)現(xiàn)def length_of_lis(nums): n len(nums) dp [1] * n ans 1 for i in range(1, n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) ans max(ans, dp[i]) return ans這個(gè)題的時(shí)間復(fù)雜度是O(n^2)因?yàn)橛袃蓪友h(huán)。它還有一個(gè)O(n log n)的優(yōu)化解法用到了貪心加二分查找但那個(gè)解法已經(jīng)不太像典型的動(dòng)態(tài)規(guī)劃了這里先不展開。5.3 案例三零錢兌換題目給若干種硬幣面額和一個(gè)目標(biāo)金額問湊出目標(biāo)金額最少需要幾枚硬幣。每種硬幣可以用無限次。第一步狀態(tài)。dp[j]表示湊出金額j所需的最少硬幣數(shù)。第二步轉(zhuǎn)移方程。對(duì)于金額j我們可以選擇任何一種面額為coin的硬幣。如果選了它就相當(dāng)于從金額j-coin轉(zhuǎn)移過來代價(jià)是1枚硬幣。所以dp[j] min(dp[j-coin] 1)對(duì)所有滿足coin j的硬幣面額取最小。第三步邊界。dp[0] 0湊出金額0不需要硬幣。其他dp[j]初始化為一個(gè)很大的數(shù)比如無窮大表示暫時(shí)無法湊出。第四步答案。dp[target]如果它還是無窮大說明無法湊出返回-1。代碼實(shí)現(xiàn)def coin_change(coins, amount): INF float(inf) dp [INF] * (amount 1) dp[0] 0 for j in range(1, amount 1): for coin in coins: if coin j: dp[j] min(dp[j], dp[j - coin] 1) return dp[amount] if dp[amount] ! INF else -1注意這里的遍歷順序外層循環(huán)遍歷金額內(nèi)層循環(huán)遍歷硬幣。為什么不能反過來因?yàn)槊糠N硬幣可以用無限次如果外層遍歷硬幣、內(nèi)層遍歷金額那對(duì)于每種硬幣你只能沿著金額遞增的方向更新一次無法實(shí)現(xiàn)“同一種硬幣用多次”的效果。外層遍歷金額、內(nèi)層遍歷硬幣才能保證每種硬幣在任意金額下都可以被重復(fù)選擇。注意背包類問題的遍歷順序非常講究。0-1背包要求每種物品只能用一次所以外層遍歷物品、內(nèi)層遍歷容量且容量從大到小完全背包要求每種物品可以用無限次所以外層遍歷物品、內(nèi)層遍歷容量且容量從小到大。如果搞反了0-1背包會(huì)變成完全背包完全背包會(huì)變成0-1背包。這個(gè)坑我踩過不止一次每次都要在草稿紙上畫一遍才放心。6. 常見問題與排查技巧實(shí)錄6.1 狀態(tài)轉(zhuǎn)移方程推不出來怎么辦這是最常見的問題。很多人卡在這一步盯著題目發(fā)呆不知道怎么從子問題推到父問題。我的經(jīng)驗(yàn)是不要硬推先手動(dòng)模擬。拿一個(gè)具體的小例子在紙上一步一步算看看每一步的答案是怎么從前面幾步的答案算出來的。比如爬樓梯你手動(dòng)算n1,2,3,4,5把結(jié)果列出來然后觀察規(guī)律。很多時(shí)候規(guī)律一出來轉(zhuǎn)移方程就跟著出來了。另一個(gè)技巧是“從最后一步倒推”。問自己到達(dá)最終狀態(tài)的前一步可能是什么把所有可能的前一步列出來然后看當(dāng)前狀態(tài)和前一步狀態(tài)之間的關(guān)系。這個(gè)方法對(duì)很多問題都有效因?yàn)樽罱K狀態(tài)往往是問題最明確的地方。如果還是推不出來那可能是狀態(tài)設(shè)計(jì)有問題?；仡^檢查一下狀態(tài)是否包含了足夠的信息是否滿足無后效性如果狀態(tài)本身就不對(duì)轉(zhuǎn)移方程當(dāng)然推不出來。6.2 邊界條件總是寫錯(cuò)怎么辦邊界條件寫錯(cuò)通常是因?yàn)闆]有想清楚“最小規(guī)模的問題是什么”。我的建議是在寫代碼之前先把n0,1,2,3的情況手動(dòng)算一遍把結(jié)果寫在紙上。然后寫代碼的時(shí)候用這些手動(dòng)算的結(jié)果去驗(yàn)證邊界條件。另外邊界條件不一定是dp[0]或dp[0][0]。有些問題的邊界是多個(gè)比如最長(zhǎng)公共子序列dp[0][j]和dp[i][0]都是邊界。有些問題的邊界需要特殊處理比如零錢兌換中dp[0]0但其他dp[j]初始化為無窮大。所以一定要根據(jù)具體問題來確定邊界不能套模板。6.3 遍歷順序搞反了怎么發(fā)現(xiàn)遍歷順序搞反的典型癥狀是代碼邏輯看起來沒問題但結(jié)果就是不對(duì)或者部分測(cè)試用例通過、部分不通過。發(fā)現(xiàn)的方法很簡(jiǎn)單在代碼里加打印把每一步的狀態(tài)值輸出出來和手動(dòng)模擬的結(jié)果對(duì)比。如果發(fā)現(xiàn)某個(gè)狀態(tài)的值依賴于一個(gè)還沒被計(jì)算的狀態(tài)那就說明遍歷順序反了。比如0-1背包問題如果內(nèi)層容量從小到大遍歷那dp[j]會(huì)依賴于dp[j-weight]已經(jīng)在本輪被更新過相當(dāng)于同一個(gè)物品被用了多次。這時(shí)候你打印dp數(shù)組會(huì)發(fā)現(xiàn)結(jié)果比正確答案大因?yàn)槲锲繁恢貜?fù)使用了。把容量改成從大到小遍歷問題就解決了。6.4 空間優(yōu)化后結(jié)果不對(duì)怎么排查空間優(yōu)化之后結(jié)果不對(duì)通常是因?yàn)閮?yōu)化后的變量沒有正確初始化或者更新順序有問題。排查方法先寫一個(gè)未優(yōu)化的版本確認(rèn)結(jié)果正確。然后逐步優(yōu)化每?jī)?yōu)化一步就對(duì)比一次結(jié)果。如果優(yōu)化后結(jié)果變了說明優(yōu)化過程中引入了bug。常見的bug包括滾動(dòng)數(shù)組的初始值沒設(shè)對(duì)、變量更新順序反了導(dǎo)致使用了新值而不是舊值、多維數(shù)組壓縮成一維時(shí)索引搞錯(cuò)了。實(shí)操心得空間優(yōu)化雖然能降低空間復(fù)雜度但會(huì)犧牲代碼的可讀性和可調(diào)試性。我的建議是除非空間確實(shí)不夠用或者面試官明確要求優(yōu)化否則優(yōu)先保證代碼的正確性和可讀性。畢竟一個(gè)能跑對(duì)的O(n)空間解法比一個(gè)跑不對(duì)的O(1)空間解法有價(jià)值得多。6.5 常見問題速查表問題現(xiàn)象可能原因排查方法解決方案結(jié)果偏大0-1背包遍歷順序反了打印dp數(shù)組檢查是否重復(fù)使用物品容量從大到小遍歷結(jié)果偏小完全背包遍歷順序反了打印dp數(shù)組檢查是否限制了物品使用次數(shù)容量從小到大遍歷部分用例通過邊界條件錯(cuò)誤手動(dòng)計(jì)算小規(guī)模用例對(duì)比結(jié)果根據(jù)實(shí)際語義修正邊界結(jié)果全錯(cuò)狀態(tài)設(shè)計(jì)錯(cuò)誤檢查狀態(tài)是否滿足無后效性重新設(shè)計(jì)狀態(tài)補(bǔ)充必要信息運(yùn)行超時(shí)狀態(tài)空間過大或轉(zhuǎn)移復(fù)雜度過高分析時(shí)間和空間復(fù)雜度精簡(jiǎn)狀態(tài)、空間優(yōu)化、或用更高效的轉(zhuǎn)移方式遞歸爆棧遞歸深度過大檢查遞歸層數(shù)改用遞推填表或增加遞歸深度限制7. 我個(gè)人在DP學(xué)習(xí)路上的一些體會(huì)動(dòng)態(tài)規(guī)劃這東西入門難精通更難。但它的難不是那種“看不懂”的難而是“想不到”的難。代碼本身往往很短十幾行就寫完了但背后的思考過程可能要好幾個(gè)小時(shí)。我自己的經(jīng)驗(yàn)是學(xué)DP一定要?jiǎng)邮帧？磩e人的題解覺得“哦原來是這樣”和自己獨(dú)立推出來完全是兩碼事。我建議每學(xué)一個(gè)新的DP類型至少獨(dú)立做五到十道同類題做到不看題解也能推出狀態(tài)和轉(zhuǎn)移方程為止。這個(gè)過程很痛苦但熬過去之后你會(huì)發(fā)現(xiàn)自己的思維方式真的變了。另外不要追求刷題數(shù)量。DP的題型是有限的經(jīng)典的就那么幾十種。與其刷兩百道題但每道都似懂非懂不如把二十道經(jīng)典題吃透每道都能講清楚狀態(tài)為什么這么設(shè)計(jì)、轉(zhuǎn)移方程為什么這么寫、邊界為什么這么定。質(zhì)量比數(shù)量重要得多。最后說一個(gè)我踩過的坑不要一上來就追求最優(yōu)解。很多人看到O(n)的解法就覺得自己O(n^2)的解法拿不出手其實(shí)完全沒必要。先把O(n^2)的解法寫對(duì)再考慮優(yōu)化。一個(gè)正確的暴力DP比一個(gè)錯(cuò)誤的優(yōu)化DP有價(jià)值一百倍。優(yōu)化是錦上添花的事正確性才是底線。這篇是動(dòng)態(tài)規(guī)劃拆解的第一篇主要把狀態(tài)設(shè)計(jì)、轉(zhuǎn)移方程、邊界條件、遍歷順序這些基礎(chǔ)但核心的東西講透了。下一篇我打算聊背包問題的幾種變體以及區(qū)間DP和樹形DP的入門思路。如果你跟著這篇的內(nèi)容把爬樓梯、最大子數(shù)組和、最長(zhǎng)遞增子序列、零錢兌換這幾個(gè)例子都親手實(shí)現(xiàn)一遍那DP的基礎(chǔ)就算是打牢了。剩下的就是多練、多想、多總結(jié)。