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