讀完本文董饰，你可以去力扣拿下如下題目：
-----------
這篇文章是我們號半年前一篇 200 多贊賞的成名之作「動態(tài)規(guī)劃詳解」的進(jìn)階版。由于賬號遷移的原因蜗搔，舊文無法被搜索到，所以我潤色了本文氯窍，并添加了更多干貨內(nèi)容唆缴，希望本文成為解決動態(tài)規(guī)劃的一部「指導(dǎo)方針」。
動態(tài)規(guī)劃問題（Dynamic Programming）應(yīng)該是很多讀者頭疼的涯呻，不過這類問題也是最具有技巧性凉驻，最有意思的。本書使用了整整一個章節(jié)專門來寫這個算法复罐，動態(tài)規(guī)劃的重要性也可見一斑涝登。
刷題刷多了就會發(fā)現(xiàn)，算法技巧就那幾個套路效诅，我們后續(xù)的動態(tài)規(guī)劃系列章節(jié)胀滚，都在使用本文的解題框架思維，如果你心里有數(shù)填帽，就會輕松很多蛛淋。所以本文放在第一章，來扒一扒動態(tài)規(guī)劃的褲子篡腌，形成一套解決這類問題的思維框架褐荷，希望能夠成為解決動態(tài)規(guī)劃問題的一部指導(dǎo)方針。本文就來講解該算法的基本套路框架嘹悼，下面上干貨叛甫。
首先，動態(tài)規(guī)劃問題的一般形式就是求最值杨伙。動態(tài)規(guī)劃其實(shí)是運(yùn)籌學(xué)的一種最優(yōu)化方法其监，只不過在計(jì)算機(jī)問題上應(yīng)用比較多，比如說讓你求最長遞增子序列呀限匣，最小編輯距離呀等等抖苦。
既然是要求最值，核心問題是什么呢米死？求解動態(tài)規(guī)劃的核心問題是窮舉锌历。因?yàn)橐笞钪担隙ㄒ阉锌尚械拇鸢父F舉出來峦筒，然后在其中找最值唄究西。
動態(tài)規(guī)劃這么簡單，就是窮舉就完事了物喷？我看到的動態(tài)規(guī)劃問題都很難奥辈摹遮斥！
首先，動態(tài)規(guī)劃的窮舉有點(diǎn)特別扇丛，因?yàn)檫@類問題存在「重疊子問題」术吗，如果暴力窮舉的話效率會極其低下，所以需要「備忘錄」或者「DP table」來優(yōu)化窮舉過程帆精，避免不必要的計(jì)算藐翎。
而且，動態(tài)規(guī)劃問題一定會具備「最優(yōu)子結(jié)構(gòu)」实幕，才能通過子問題的最值得到原問題的最值。
另外堤器，雖然動態(tài)規(guī)劃的核心思想就是窮舉求最值昆庇，但是問題可以千變?nèi)f化，窮舉所有可行解其實(shí)并不是一件容易的事闸溃，只有列出正確的「狀態(tài)轉(zhuǎn)移方程」才能正確地窮舉整吆。
以上提到的重疊子問題、最優(yōu)子結(jié)構(gòu)辉川、狀態(tài)轉(zhuǎn)移方程就是動態(tài)規(guī)劃三要素表蝙。具體什么意思等會會舉例詳解，但是在實(shí)際的算法問題中乓旗，寫出狀態(tài)轉(zhuǎn)移方程是最困難的府蛇，這也就是為什么很多朋友覺得動態(tài)規(guī)劃問題困難的原因，我來提供我研究出來的一個思維框架屿愚，輔助你思考狀態(tài)轉(zhuǎn)移方程：
明確 base case -> 明確「狀態(tài)」-> 明確「選擇」 -> 定義 dp 數(shù)組/函數(shù)的含義汇跨。
按上面的套路走，最后的結(jié)果就可以套這個框架：
# 初始化 base case
dp[0][0][...] = base
# 進(jìn)行狀態(tài)轉(zhuǎn)移
for 狀態(tài)1 in 狀態(tài)1的所有取值：
for 狀態(tài)2 in 狀態(tài)2的所有取值：
for ...
dp[狀態(tài)1][狀態(tài)2][...] = 求最值(選擇1妆距，選擇2...)
下面通過斐波那契數(shù)列問題和湊零錢問題來詳解動態(tài)規(guī)劃的基本原理穷遂。前者主要是讓你明白什么是重疊子問題（斐波那契數(shù)列沒有求最值，所以嚴(yán)格來說不是動態(tài)規(guī)劃問題）娱据，后者主要舉集中于如何列出狀態(tài)轉(zhuǎn)移方程蚪黑。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目中剩，全部發(fā)布在 labuladong的算法小抄忌穿，持續(xù)更新。建議收藏咽安，按照我的文章順序刷題伴网，掌握各種算法套路后投再入題海就如魚得水了。
一妆棒、斐波那契數(shù)列
請讀者不要嫌棄這個例子簡單澡腾，只有簡單的例子才能讓你把精力充分集中在算法背后的通用思想和技巧上沸伏，而不會被那些隱晦的細(xì)節(jié)問題搞的莫名其妙。想要困難的例子动分，歷史文章里有的是毅糟。
1、暴力遞歸
斐波那契數(shù)列的數(shù)學(xué)形式就是遞歸的澜公，寫成代碼就是這樣：
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
這個不用多說了姆另，學(xué)校老師講遞歸的時候似乎都是拿這個舉例。我們也知道這樣寫代碼雖然簡潔易懂坟乾，但是十分低效迹辐，低效在哪里？假設(shè) n = 20甚侣，請畫出遞歸樹：
PS：但凡遇到需要遞歸的問題明吩，最好都畫出遞歸樹，這對你分析算法的復(fù)雜度殷费，尋找算法低效的原因都有巨大幫助印荔。
這個遞歸樹怎么理解？就是說想要計(jì)算原問題 f(20)详羡，我就得先計(jì)算出子問題 f(19) 和 f(18)仍律，然后要計(jì)算 f(19)，我就要先算出子問題 f(18) 和 f(17)实柠，以此類推水泉。最后遇到 f(1) 或者 f(2) 的時候，結(jié)果已知窒盐，就能直接返回結(jié)果茶行，遞歸樹不再向下生長了。
遞歸算法的時間復(fù)雜度怎么計(jì)算登钥？就是用子問題個數(shù)乘以解決一個子問題需要的時間畔师。
首先計(jì)算子問題個數(shù)，即遞歸樹中節(jié)點(diǎn)的總數(shù)牧牢。顯然二叉樹節(jié)點(diǎn)總數(shù)為指數(shù)級別看锉，所以子問題個數(shù)為 O(2^n)。
然后計(jì)算解決一個子問題的時間塔鳍，在本算法中伯铣，沒有循環(huán)，只有 f(n - 1) + f(n - 2) 一個加法操作轮纫，時間為 O(1)腔寡。
所以，這個算法的時間復(fù)雜度為二者相乘掌唾，即 O(2^n)放前，指數(shù)級別忿磅，爆炸。
觀察遞歸樹凭语，很明顯發(fā)現(xiàn)了算法低效的原因：存在大量重復(fù)計(jì)算葱她，比如 f(18) 被計(jì)算了兩次，而且你可以看到似扔，以 f(18) 為根的這個遞歸樹體量巨大吨些，多算一遍，會耗費(fèi)巨大的時間炒辉。更何況豪墅，還不止 f(18) 這一個節(jié)點(diǎn)被重復(fù)計(jì)算，所以這個算法及其低效黔寇。
這就是動態(tài)規(guī)劃問題的第一個性質(zhì)：重疊子問題但校。下面，我們想辦法解決這個問題啡氢。
2、帶備忘錄的遞歸解法
明確了問題术裸，其實(shí)就已經(jīng)把問題解決了一半倘是。即然耗時的原因是重復(fù)計(jì)算，那么我們可以造一個「備忘錄」袭艺，每次算出某個子問題的答案后別急著返回搀崭，先記到「備忘錄」里再返回；每次遇到一個子問題先去「備忘錄」里查一查猾编，如果發(fā)現(xiàn)之前已經(jīng)解決過這個問題了瘤睹，直接把答案拿出來用，不要再耗時去計(jì)算了答倡。
一般使用一個數(shù)組充當(dāng)這個「備忘錄」轰传，當(dāng)然你也可以使用哈希表（字典），思想都是一樣的瘪撇。
int fib(int N) {
if (N < 1) return 0;
// 備忘錄全初始化為 0
vector<int> memo(N + 1, 0);
// 進(jìn)行帶備忘錄的遞歸
return helper(memo, N);
}
int helper(vector<int>& memo, int n) {
// base case
if (n == 1 || n == 2) return 1;
// 已經(jīng)計(jì)算過
if (memo[n] != 0) return memo[n];
memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
return memo[n];
}
現(xiàn)在获茬，畫出遞歸樹，你就知道「備忘錄」到底做了什么倔既。
實(shí)際上恕曲，帶「備忘錄」的遞歸算法，把一棵存在巨量冗余的遞歸樹通過「剪枝」渤涌，改造成了一幅不存在冗余的遞歸圖佩谣，極大減少了子問題（即遞歸圖中節(jié)點(diǎn)）的個數(shù)。
遞歸算法的時間復(fù)雜度怎么計(jì)算实蓬？就是用子問題個數(shù)乘以解決一個子問題需要的時間茸俭。
子問題個數(shù)吊履，即圖中節(jié)點(diǎn)的總數(shù)，由于本算法不存在冗余計(jì)算瓣履，子問題就是 f(1), f(2), f(3) ... f(20)率翅，數(shù)量和輸入規(guī)模 n = 20 成正比，所以子問題個數(shù)為 O(n)袖迎。
解決一個子問題的時間冕臭，同上，沒有什么循環(huán)燕锥，時間為 O(1)辜贵。
所以，本算法的時間復(fù)雜度是 O(n)归形。比起暴力算法托慨，是降維打擊。
至此暇榴，帶備忘錄的遞歸解法的效率已經(jīng)和迭代的動態(tài)規(guī)劃解法一樣了攒盈。實(shí)際上，這種解法和迭代的動態(tài)規(guī)劃已經(jīng)差不多了婿崭，只不過這種方法叫做「自頂向下」宰啦，動態(tài)規(guī)劃叫做「自底向上」。
啥叫「自頂向下」奸例？注意我們剛才畫的遞歸樹（或者說圖）彬犯，是從上向下延伸，都是從一個規(guī)模較大的原問題比如說 f(20)查吊，向下逐漸分解規(guī)模谐区，直到 f(1) 和 f(2) 這兩個 base case，然后逐層返回答案逻卖，這就叫「自頂向下」宋列。
啥叫「自底向上」？反過來评也，我們直接從最底下虚茶，最簡單，問題規(guī)模最小的 f(1) 和 f(2) 開始往上推仇参，直到推到我們想要的答案 f(20)嘹叫，這就是動態(tài)規(guī)劃的思路，這也是為什么動態(tài)規(guī)劃一般都脫離了遞歸诈乒，而是由循環(huán)迭代完成計(jì)算罩扇。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄喂饥，持續(xù)更新消约。建議收藏，按照我的文章順序刷題员帮，掌握各種算法套路后投再入題海就如魚得水了或粮。
3、dp 數(shù)組的迭代解法
有了上一步「備忘錄」的啟發(fā)捞高，我們可以把這個「備忘錄」獨(dú)立出來成為一張表氯材，就叫做 DP table 吧，在這張表上完成「自底向上」的推算豈不美哉硝岗！
int fib(int N) {
vector<int> dp(N + 1, 0);
// base case
dp[1] = dp[2] = 1;
for (int i = 3; i <= N; i++)
dp[i] = dp[i - 1] + dp[i - 2];
return dp[N];
}
畫個圖就很好理解了氢哮，而且你發(fā)現(xiàn)這個 DP table 特別像之前那個「剪枝」后的結(jié)果，只是反過來算而已型檀。實(shí)際上冗尤，帶備忘錄的遞歸解法中的「備忘錄」，最終完成后就是這個 DP table胀溺，所以說這兩種解法其實(shí)是差不多的裂七，大部分情況下，效率也基本相同仓坞。
這里背零，引出「狀態(tài)轉(zhuǎn)移方程」這個名詞，實(shí)際上就是描述問題結(jié)構(gòu)的數(shù)學(xué)形式：
為啥叫「狀態(tài)轉(zhuǎn)移方程」扯躺？其實(shí)就是為了聽起來高端。你把 f(n) 想做一個狀態(tài) n蝎困，這個狀態(tài) n 是由狀態(tài) n - 1 和狀態(tài) n - 2 相加轉(zhuǎn)移而來录语，這就叫狀態(tài)轉(zhuǎn)移，僅此而已禾乘。
你會發(fā)現(xiàn)澎埠，上面的幾種解法中的所有操作，例如 return f(n - 1) + f(n - 2)始藕，dp[i] = dp[i - 1] + dp[i - 2]蒲稳，以及對備忘錄或 DP table 的初始化操作，都是圍繞這個方程式的不同表現(xiàn)形式伍派〗可見列出「狀態(tài)轉(zhuǎn)移方程」的重要性，它是解決問題的核心诉植。而且很容易發(fā)現(xiàn)祥国，其實(shí)狀態(tài)轉(zhuǎn)移方程直接代表著暴力解法。
千萬不要看不起暴力解，動態(tài)規(guī)劃問題最困難的就是寫出這個暴力解舌稀，即狀態(tài)轉(zhuǎn)移方程啊犬。只要寫出暴力解，優(yōu)化方法無非是用備忘錄或者 DP table壁查，再無奧妙可言觉至。
這個例子的最后，講一個細(xì)節(jié)優(yōu)化睡腿。細(xì)心的讀者會發(fā)現(xiàn)语御，根據(jù)斐波那契數(shù)列的狀態(tài)轉(zhuǎn)移方程，當(dāng)前狀態(tài)只和之前的兩個狀態(tài)有關(guān)嫉到，其實(shí)并不需要那么長的一個 DP table 來存儲所有的狀態(tài)沃暗，只要想辦法存儲之前的兩個狀態(tài)就行了。所以何恶，可以進(jìn)一步優(yōu)化孽锥，把空間復(fù)雜度降為 O(1)：
int fib(int n) {
if (n == 2 || n == 1)
return 1;
int prev = 1, curr = 1;
for (int i = 3; i <= n; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
這個技巧就是所謂的「狀態(tài)壓縮」，如果我們發(fā)現(xiàn)每次狀態(tài)轉(zhuǎn)移只需要 DP table 中的一部分细层，那么可以嘗試用狀態(tài)壓縮來縮小 DP table 的大小惜辑，只記錄必要的數(shù)據(jù)，上述例子就相當(dāng)于把DP table 的大小從 n 縮小到 2疫赎。后續(xù)的動態(tài)規(guī)劃章節(jié)中我們還會看到這樣的例子盛撑，一般來說是把一個二維的 DP table 壓縮成一維，即把空間復(fù)雜度從 O(n^2) 壓縮到 O(n)捧搞。
有人會問抵卫，動態(tài)規(guī)劃的另一個重要特性「最優(yōu)子結(jié)構(gòu)」，怎么沒有涉及胎撇？下面會涉及介粘。斐波那契數(shù)列的例子嚴(yán)格來說不算動態(tài)規(guī)劃，因?yàn)闆]有涉及求最值晚树，以上旨在說明重疊子問題的消除方法姻采，演示得到最優(yōu)解法逐步求精的過程。下面爵憎，看第二個例子慨亲，湊零錢問題。
二宝鼓、湊零錢問題
先看下題目：給你 k 種面值的硬幣刑棵，面值分別為 c1, c2 ... ck，每種硬幣的數(shù)量無限愚铡，再給一個總金額 amount铐望，問你最少需要幾枚硬幣湊出這個金額，如果不可能湊出，算法返回 -1 正蛙。算法的函數(shù)簽名如下：
// coins 中是可選硬幣面值督弓，amount 是目標(biāo)金額
int coinChange(int[] coins, int amount);
比如說 k = 3，面值分別為 1乒验，2愚隧，5，總金額 amount = 11锻全。那么最少需要 3 枚硬幣湊出狂塘，即 11 = 5 + 5 + 1。
你認(rèn)為計(jì)算機(jī)應(yīng)該如何解決這個問題鳄厌？顯然荞胡，就是把所有肯能的湊硬幣方法都窮舉出來，然后找找看最少需要多少枚硬幣了嚎。
1泪漂、暴力遞歸
首先，這個問題是動態(tài)規(guī)劃問題歪泳，因?yàn)樗哂小缸顑?yōu)子結(jié)構(gòu)」的萝勤。要符合「最優(yōu)子結(jié)構(gòu)」，子問題間必須互相獨(dú)立呐伞。啥叫相互獨(dú)立敌卓？你肯定不想看數(shù)學(xué)證明，我用一個直觀的例子來講解伶氢。
比如說趟径，假設(shè)你考試，每門科目的成績都是互相獨(dú)立的癣防。你的原問題是考出最高的總成績蜗巧，那么你的子問題就是要把語文考到最高，數(shù)學(xué)考到最高…… 為了每門課考到最高劣砍，你要把每門課相應(yīng)的選擇題分?jǐn)?shù)拿到最高惧蛹，填空題分?jǐn)?shù)拿到最高…… 當(dāng)然扇救，最終就是你每門課都是滿分刑枝，這就是最高的總成績。
得到了正確的結(jié)果：最高的總成績就是總分迅腔。因?yàn)檫@個過程符合最優(yōu)子結(jié)構(gòu)装畅，“每門科目考到最高”這些子問題是互相獨(dú)立，互不干擾的沧烈。
但是掠兄，如果加一個條件：你的語文成績和數(shù)學(xué)成績會互相制約，數(shù)學(xué)分?jǐn)?shù)高，語文分?jǐn)?shù)就會降低蚂夕，反之亦然迅诬。這樣的話，顯然你能考到的最高總成績就達(dá)不到總分了婿牍，按剛才那個思路就會得到錯誤的結(jié)果侈贷。因?yàn)樽訂栴}并不獨(dú)立，語文數(shù)學(xué)成績無法同時最優(yōu)等脂，所以最優(yōu)子結(jié)構(gòu)被破壞俏蛮。
回到湊零錢問題，為什么說它符合最優(yōu)子結(jié)構(gòu)呢上遥？比如你想求 amount = 11 時的最少硬幣數(shù)（原問題）搏屑，如果你知道湊出 amount = 10 的最少硬幣數(shù)（子問題），你只需要把子問題的答案加一（再選一枚面值為 1 的硬幣）就是原問題的答案粉楚。因?yàn)橛矌诺臄?shù)量是沒有限制的辣恋，所以子問題之間沒有相互制，是互相獨(dú)立的解幼。
PS：關(guān)于最優(yōu)子結(jié)構(gòu)的問題抑党，后文動態(tài)規(guī)劃答疑篇 還會再舉例探討。
那么撵摆，既然知道了這是個動態(tài)規(guī)劃問題底靠，就要思考如何列出正確的狀態(tài)轉(zhuǎn)移方程？
1特铝、確定 base case暑中，這個很簡單，顯然目標(biāo)金額 amount 為 0 時算法返回 0鲫剿，因?yàn)椴恍枰魏斡矌啪鸵呀?jīng)湊出目標(biāo)金額了鳄逾。
2、確定「狀態(tài)」灵莲，也就是原問題和子問題中會變化的變量雕凹。由于硬幣數(shù)量無限，硬幣的面額也是題目給定的政冻，只有目標(biāo)金額會不斷地向 base case 靠近枚抵，所以唯一的「狀態(tài)」就是目標(biāo)金額 amount。
3明场、確定「選擇」汽摹，也就是導(dǎo)致「狀態(tài)」產(chǎn)生變化的行為。目標(biāo)金額為什么變化呢苦锨，因?yàn)槟阍谶x擇硬幣逼泣，你每選擇一枚硬幣趴泌，就相當(dāng)于減少了目標(biāo)金額。所以說所有硬幣的面值拉庶，就是你的「選擇」嗜憔。
4、明確 dp 函數(shù)/數(shù)組的定義氏仗。我們這里講的是自頂向下的解法痹筛，所以會有一個遞歸的 dp 函數(shù)，一般來說函數(shù)的參數(shù)就是狀態(tài)轉(zhuǎn)移中會變化的量廓鞠，也就是上面說到的「狀態(tài)」帚稠；函數(shù)的返回值就是題目要求我們計(jì)算的量。就本題來說床佳，狀態(tài)只有一個滋早，即「目標(biāo)金額」，題目要求我們計(jì)算湊出目標(biāo)金額所需的最少硬幣數(shù)量砌们。所以我們可以這樣定義 dp 函數(shù)：
dp(n) 的定義：輸入一個目標(biāo)金額 n杆麸，返回湊出目標(biāo)金額 n 的最少硬幣數(shù)量。
搞清楚上面這幾個關(guān)鍵點(diǎn)浪感，解法的偽碼就可以寫出來了：
# 偽碼框架
def coinChange(coins: List[int], amount: int):
# 定義：要湊出金額 n昔头，至少要 dp(n) 個硬幣
def dp(n):
# 做選擇，選擇需要硬幣最少的那個結(jié)果
for coin in coins:
res = min(res, 1 + dp(n - coin))
return res
# 題目要求的最終結(jié)果是 dp(amount)
return dp(amount)
根據(jù)偽碼影兽，我們加上 base case 即可得到最終的答案揭斧。顯然目標(biāo)金額為 0 時，所需硬幣數(shù)量為 0峻堰；當(dāng)目標(biāo)金額小于 0 時讹开，無解，返回 -1：
def coinChange(coins: List[int], amount: int):
def dp(n):
# base case
if n == 0: return 0
if n < 0: return -1
# 求最小值捐名，所以初始化為正無窮
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
# 子問題無解旦万，跳過
if subproblem == -1: continue
res = min(res, 1 + subproblem)
return res if res != float('INF') else -1
return dp(amount)
至此，狀態(tài)轉(zhuǎn)移方程其實(shí)已經(jīng)完成了镶蹋，以上算法已經(jīng)是暴力解法了成艘，以上代碼的數(shù)學(xué)形式就是狀態(tài)轉(zhuǎn)移方程：
至此，這個問題其實(shí)就解決了贺归，只不過需要消除一下重疊子問題淆两，比如 amount = 11, coins = {1,2,5} 時畫出遞歸樹看看：
遞歸算法的時間復(fù)雜度分析：子問題總數(shù) x 每個子問題的時間。
子問題總數(shù)為遞歸樹節(jié)點(diǎn)個數(shù)牧氮，這個比較難看出來琼腔，是 O(n^k)瑰枫，總之是指數(shù)級別的踱葛。每個子問題中含有一個 for 循環(huán)丹莲，復(fù)雜度為 O(k)。所以總時間復(fù)雜度為 O(k * n^k)尸诽，指數(shù)級別甥材。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目性含，全部發(fā)布在 labuladong的算法小抄洲赵，持續(xù)更新。建議收藏商蕴，按照我的文章順序刷題叠萍，掌握各種算法套路后投再入題海就如魚得水了。
2绪商、帶備忘錄的遞歸
類似之前斐波那契數(shù)列的例子苛谷，只需要稍加修改，就可以通過備忘錄消除子問題：
def coinChange(coins: List[int], amount: int):
# 備忘錄
memo = dict()
def dp(n):
# 查備忘錄格郁，避免重復(fù)計(jì)算
if n in memo: return memo[n]
# base case
if n == 0: return 0
if n < 0: return -1
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
if subproblem == -1: continue
res = min(res, 1 + subproblem)
# 記入備忘錄
memo[n] = res if res != float('INF') else -1
return memo[n]
return dp(amount)
不畫圖了腹殿，很顯然「備忘錄」大大減小了子問題數(shù)目，完全消除了子問題的冗余例书，所以子問題總數(shù)不會超過金額數(shù) n锣尉，即子問題數(shù)目為 O(n)。處理一個子問題的時間不變决采，仍是 O(k)自沧，所以總的時間復(fù)雜度是 O(kn)。
3树瞭、dp 數(shù)組的迭代解法
當(dāng)然暂幼，我們也可以自底向上使用 dp table 來消除重疊子問題，關(guān)于「狀態(tài)」「選擇」和 base case 與之前沒有區(qū)別移迫，dp 數(shù)組的定義和剛才 dp 函數(shù)類似旺嬉，也是把「狀態(tài)」，也就是目標(biāo)金額作為變量厨埋。不過 dp 函數(shù)體現(xiàn)在函數(shù)參數(shù)邪媳，而 dp 數(shù)組體現(xiàn)在數(shù)組索引：
dp 數(shù)組的定義：當(dāng)目標(biāo)金額為 i 時，至少需要 dp[i] 枚硬幣湊出荡陷。
根據(jù)我們文章開頭給出的動態(tài)規(guī)劃代碼框架可以寫出如下解法：
int coinChange(vector<int>& coins, int amount) {
// 數(shù)組大小為 amount + 1雨效，初始值也為 amount + 1
vector<int> dp(amount + 1, amount + 1);
// base case
dp[0] = 0;
// 外層 for 循環(huán)在遍歷所有狀態(tài)的所有取值
for (int i = 0; i < dp.size(); i++) {
// 內(nèi)層 for 循環(huán)在求所有選擇的最小值
for (int coin : coins) {
// 子問題無解，跳過
if (i - coin < 0) continue;
dp[i] = min(dp[i], 1 + dp[i - coin]);
}
}
return (dp[amount] == amount + 1) ? -1 : dp[amount];
}
PS：為啥 dp 數(shù)組初始化為 amount + 1 呢废赞，因?yàn)闇惓?amount 金額的硬幣數(shù)最多只可能等于 amount（全用 1 元面值的硬幣）徽龟，所以初始化為 amount + 1 就相當(dāng)于初始化為正無窮，便于后續(xù)取最小值唉地。
三据悔、最后總結(jié)
第一個斐波那契數(shù)列的問題传透，解釋了如何通過「備忘錄」或者「dp table」的方法來優(yōu)化遞歸樹，并且明確了這兩種方法本質(zhì)上是一樣的极颓，只是自頂向下和自底向上的不同而已朱盐。
第二個湊零錢的問題，展示了如何流程化確定「狀態(tài)轉(zhuǎn)移方程」菠隆，只要通過狀態(tài)轉(zhuǎn)移方程寫出暴力遞歸解兵琳，剩下的也就是優(yōu)化遞歸樹，消除重疊子問題而已骇径。
如果你不太了解動態(tài)規(guī)劃躯肌，還能看到這里，真得給你鼓掌破衔，相信你已經(jīng)掌握了這個算法的設(shè)計(jì)技巧羡榴。
計(jì)算機(jī)解決問題其實(shí)沒有任何奇技淫巧，它唯一的解決辦法就是窮舉运敢，窮舉所有可能性校仑。算法設(shè)計(jì)無非就是先思考“如何窮舉”，然后再追求“如何聰明地窮舉”传惠。
列出動態(tài)轉(zhuǎn)移方程迄沫，就是在解決“如何窮舉”的問題。之所以說它難卦方，一是因?yàn)楹芏喔F舉需要遞歸實(shí)現(xiàn)羊瘩，二是因?yàn)橛械膯栴}本身的解空間復(fù)雜，不那么容易窮舉完整盼砍。
備忘錄尘吗、DP table 就是在追求“如何聰明地窮舉”。用空間換時間的思路浇坐，是降低時間復(fù)雜度的不二法門睬捶，除此之外，試問近刘，還能玩出啥花活擒贸？
之后我們會有一章專門講解動態(tài)規(guī)劃問題，如果有任何問題都可以隨時回來重讀本文觉渴，希望讀者在閱讀每個題目和解法時介劫，多往「狀態(tài)」和「選擇」上靠，才能對這套框架產(chǎn)生自己的理解案淋，運(yùn)用自如座韵。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目踢京，建議收藏誉碴！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star宦棺，歡迎標(biāo)星！
