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