既然是要求最值，核心問題是什么呢？求解動(dòng)態(tài)規(guī)劃的核心問題是窮舉。因?yàn)橐笞钪?，肯定要把所有可行的答案窮舉出來，然后在其中找最值唄。

動(dòng)態(tài)規(guī)劃就這么簡單，就是窮舉就完事了？我看到的動(dòng)態(tài)規(guī)劃問題都很難啊！

首先，動(dòng)態(tài)規(guī)劃的窮舉有點(diǎn)特別，因?yàn)檫@類問題存在「重疊子問題」，如果暴力窮舉的話效率會(huì)極其低下，所以需要「備忘錄」或者「DP table」來優(yōu)化窮舉過程，避免不必要的計(jì)算。

而且，動(dòng)態(tài)規(guī)劃問題一定會(huì)具備「最優(yōu)子結(jié)構(gòu)」，才能通過子問題的最值得到原問題的最值。

另外，雖然動(dòng)態(tài)規(guī)劃的核心思想就是窮舉求最值，但是問題可以千變?nèi)f化，窮舉所有可行解其實(shí)并不是一件容易的事，只有列出正確的「狀態(tài)轉(zhuǎn)移方程」才能正確地窮舉。

以上提到的重疊子問題、最優(yōu)子結(jié)構(gòu)、狀態(tài)轉(zhuǎn)移方程就是動(dòng)態(tài)規(guī)劃三要素。具體什么意思等會(huì)會(huì)舉例詳解，但是在實(shí)際的算法問題中，寫出狀態(tài)轉(zhuǎn)移方程是最困難的，這也就是為什么很多朋友覺得動(dòng)態(tài)規(guī)劃問題困難的原因，我來提供我研究出來的一個(gè)思維框架，輔助你思考狀態(tài)轉(zhuǎn)移方程：

明確「狀態(tài)」 -> 定義 dp 數(shù)組/函數(shù)的含義 -> 明確「選擇」-> 明確 base case。

下面通過斐波那契數(shù)列問題和湊零錢問題來詳解動(dòng)態(tài)規(guī)劃的基本原理。前者主要是讓你明白什么是重疊子問題（斐波那契數(shù)列嚴(yán)格來說不是動(dòng)態(tài)規(guī)劃問題），后者主要集中于如何列出狀態(tài)轉(zhuǎn)移方程。

請讀者不要嫌棄這個(gè)例子簡單，只有簡單的例子才能讓你把精力充分集中在算法背后的通用思想和技巧上，而不會(huì)被那些隱晦的細(xì)節(jié)問題搞的莫名其妙。想要困難的例子，歷史文章里有的是。

一、斐波那契數(shù)列

1、暴力遞歸

斐波那契數(shù)列的數(shù)學(xué)形式就是遞歸的，寫成代碼就是這樣：

int?fib(int?N)?{
????if?(N?==?1?||?N?==?2)?return?1;
????return?fib(N?-?1)?+?fib(N?-?2);
}

這個(gè)不用多說了，學(xué)校老師講遞歸的時(shí)候似乎都是拿這個(gè)舉例。我們也知道這樣寫代碼雖然簡潔易懂，但是十分低效，低效在哪里？假設(shè) n = 20，請畫出遞歸樹。

PS：但凡遇到需要遞歸的問題，最好都畫出遞歸樹，這對你分析算法的復(fù)雜度，尋找算法低效的原因都有巨大幫助。

這個(gè)遞歸樹怎么理解？就是說想要計(jì)算原問題f(20)，我就得先計(jì)算出子問題f(19)和f(18)，然后要計(jì)算f(19)，我就要先算出子問題f(18)和f(17)，以此類推。最后遇到f(1)或者f(2)的時(shí)候，結(jié)果已知，就能直接返回結(jié)果，遞歸樹不再向下生長了。

遞歸算法的時(shí)間復(fù)雜度怎么計(jì)算？子問題個(gè)數(shù)乘以解決一個(gè)子問題需要的時(shí)間。

子問題個(gè)數(shù)，即遞歸樹中節(jié)點(diǎn)的總數(shù)。顯然二叉樹節(jié)點(diǎn)總數(shù)為指數(shù)級別，所以子問題個(gè)數(shù)為 O(2^n)。

解決一個(gè)子問題的時(shí)間，在本算法中，沒有循環(huán)，只有 f(n - 1) + f(n - 2) 一個(gè)加法操作，時(shí)間為 O(1)。

所以，這個(gè)算法的時(shí)間復(fù)雜度為 O(2^n)，指數(shù)級別，爆炸。

觀察遞歸樹，很明顯發(fā)現(xiàn)了算法低效的原因：存在大量重復(fù)計(jì)算，比如f(18)被計(jì)算了兩次，而且你可以看到，以f(18)為根的這個(gè)遞歸樹體量巨大，多算一遍，會(huì)耗費(fèi)巨大的時(shí)間。更何況，還不止f(18)這一個(gè)節(jié)點(diǎn)被重復(fù)計(jì)算，所以這個(gè)算法及其低效。

這就是動(dòng)態(tài)規(guī)劃問題的第一個(gè)性質(zhì)：重疊子問題。下面，我們想辦法解決這個(gè)問題。

2、帶備忘錄的遞歸解法

明確了問題，其實(shí)就已經(jīng)把問題解決了一半。即然耗時(shí)的原因是重復(fù)計(jì)算，那么我們可以造一個(gè)「備忘錄」，每次算出某個(gè)子問題的答案后別急著返回，先記到「備忘錄」里再返回；每次遇到一個(gè)子問題先去「備忘錄」里查一查，如果發(fā)現(xiàn)之前已經(jīng)解決過這個(gè)問題了，直接把答案拿出來用，不要再耗時(shí)去計(jì)算了。

一般使用一個(gè)數(shù)組充當(dāng)這個(gè)「備忘錄」，當(dāng)然你也可以使用哈希表（字典），思想都是一樣的。

int?fib(int?N)?{
????if?(N?1)?return?0;
????//?備忘錄全初始化為?0
????vector<int>?memo(N?+?1,?0);
????//?初始化最簡情況
????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)）的個(gè)數(shù)。

遞歸算法的時(shí)間復(fù)雜度怎么算？子問題個(gè)數(shù)乘以解決一個(gè)子問題需要的時(shí)間。

子問題個(gè)數(shù)，即圖中節(jié)點(diǎn)的總數(shù)，由于本算法不存在冗余計(jì)算，子問題就是f(1),f(2),f(3)…f(20)，數(shù)量和輸入規(guī)模 n = 20 成正比，所以子問題個(gè)數(shù)為 O(n)。

解決一個(gè)子問題的時(shí)間，同上，沒有什么循環(huán)，時(shí)間為 O(1)。

所以，本算法的時(shí)間復(fù)雜度是 O(n)。比起暴力算法，是降維打擊。

至此，帶備忘錄的遞歸解法的效率已經(jīng)和迭代的動(dòng)態(tài)規(guī)劃一樣了。實(shí)際上，這種解法和迭代的動(dòng)態(tài)規(guī)劃思想已經(jīng)差不多，只不過這種方法叫做「自頂向下」，動(dòng)態(tài)規(guī)劃叫做「自底向上」。

啥叫「自頂向下」？注意我們剛才畫的遞歸樹（或者說圖），是從上向下延伸，都是從一個(gè)規(guī)模較大的原問題比如說f(20)，向下逐漸分解規(guī)模，直到f(1)和f(2)觸底，然后逐層返回答案，這就叫「自頂向下」。

啥叫「自底向上」？反過來，我們直接從最底下，最簡單，問題規(guī)模最小的f(1)和f(2)開始往上推，直到推到我們想要的答案f(20)，這就是動(dòng)態(tài)規(guī)劃的思路，這也是為什么動(dòng)態(tài)規(guī)劃一般都脫離了遞歸，而是由循環(huán)迭代完成計(jì)算。

3、dp 數(shù)組的迭代解法

有了上一步「備忘錄」的啟發(fā)，我們可以把這個(gè)「備忘錄」獨(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];
}

畫個(gè)圖就很好理解了，而且你發(fā)現(xiàn)這個(gè) DP table 特別像之前那個(gè)「剪枝」后的結(jié)果，只是反過來算而已。實(shí)際上，帶備忘錄的遞歸解法中的「備忘錄」，最終完成后就是這個(gè) DP table，所以說這兩種解法其實(shí)是差不多的，大部分情況下，效率也基本相同。

這里，引出「狀態(tài)轉(zhuǎn)移方程」這個(gè)名詞，實(shí)際上就是描述問題結(jié)構(gòu)的數(shù)學(xué)形式：

為啥叫「狀態(tài)轉(zhuǎn)移方程」？為了聽起來高端。你把 f(n) 想做一個(gè)狀態(tài) n，這個(gè)狀態(tài) n 是由狀態(tài) n - 1 和狀態(tài) n - 2 相加轉(zhuǎn)移而來，這就叫狀態(tài)轉(zhuǎn)移，僅此而已。

你會(huì)發(fā)現(xiàn)，上面的幾種解法中的所有操作，例如 return f(n - 1) + f(n - 2)，dp[i] = dp[i - 1] + dp[i - 2]，以及對備忘錄或 DP table 的初始化操作，都是圍繞這個(gè)方程式的不同表現(xiàn)形式?？梢娏谐觥笭顟B(tài)轉(zhuǎn)移方程」的重要性，它是解決問題的核心。很容易發(fā)現(xiàn)，其實(shí)狀態(tài)轉(zhuǎn)移方程直接代表著暴力解法。

千萬不要看不起暴力解，動(dòng)態(tài)規(guī)劃問題最困難的就是寫出狀態(tài)轉(zhuǎn)移方程，即這個(gè)暴力解。優(yōu)化方法無非是用備忘錄或者 DP table，再無奧妙可言。

這個(gè)例子的最后，講一個(gè)細(xì)節(jié)優(yōu)化。細(xì)心的讀者會(huì)發(fā)現(xiàn)，根據(jù)斐波那契數(shù)列的狀態(tài)轉(zhuǎn)移方程，當(dāng)前狀態(tài)只和之前的兩個(gè)狀態(tài)有關(guān)，其實(shí)并不需要那么長的一個(gè) DP table 來存儲(chǔ)所有的狀態(tài)，只要想辦法存儲(chǔ)之前的兩個(gè)狀態(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;
}

有人會(huì)問，動(dòng)態(tài)規(guī)劃的另一個(gè)重要特性「最優(yōu)子結(jié)構(gòu)」，怎么沒有涉及？下面會(huì)涉及。斐波那契數(shù)列的例子嚴(yán)格來說不算動(dòng)態(tài)規(guī)劃，因?yàn)闆]有涉及求最值，以上旨在演示算法設(shè)計(jì)螺旋上升的過程。

下面，看第二個(gè)例子，湊零錢問題。

二、湊零錢問題

先看下題目：給你k種面值的硬幣，面值分別為c1, c2 ... ck，每種硬幣的數(shù)量無限，再給一個(gè)總金額amount，問你最少需要幾枚硬幣湊出這個(gè)金額，如果不可能湊出，算法返回 -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)該如何解決這個(gè)問題？顯然，就是把所有肯能的湊硬幣方法都窮舉出來，然后找找看最少需要多少枚硬幣。

1、暴力遞歸

首先，這個(gè)問題是動(dòng)態(tài)規(guī)劃問題，因?yàn)樗哂小缸顑?yōu)子結(jié)構(gòu)」。要符合「最優(yōu)子結(jié)構(gòu)」，子問題間必須互相獨(dú)立。啥叫相互獨(dú)立？你肯定不想看數(shù)學(xué)證明，我用一個(gè)直觀的例子來講解。

比如說，你的原問題是考出最高的總成績，那么你的子問題就是要把語文考到最高，數(shù)學(xué)考到最高…… 為了每門課考到最高，你要把每門課相應(yīng)的選擇題分?jǐn)?shù)拿到最高，填空題分?jǐn)?shù)拿到最高…… 當(dāng)然，最終就是你每門課都是滿分，這就是最高的總成績。

得到了正確的結(jié)果：最高的總成績就是總分。因?yàn)檫@個(gè)過程符合最優(yōu)子結(jié)構(gòu)，“每門科目考到最高”這些子問題是互相獨(dú)立，互不干擾的。

但是，如果加一個(gè)條件：你的語文成績和數(shù)學(xué)成績會(huì)互相制約，此消彼長。這樣的話，顯然你能考到的最高總成績就達(dá)不到總分了，按剛才那個(gè)思路就會(huì)得到錯(cuò)誤的結(jié)果。因?yàn)樽訂栴}并不獨(dú)立，語文數(shù)學(xué)成績無法同時(shí)最優(yōu)，所以最優(yōu)子結(jié)構(gòu)被破壞。

回到湊零錢問題，為什么說它符合最優(yōu)子結(jié)構(gòu)呢？比如你想求amount = 11時(shí)的最少硬幣數(shù)（原問題），如果你知道湊出amount = 10的最少硬幣數(shù)（子問題），你只需要把子問題的答案加一（再選一枚面值為 1 的硬幣）就是原問題的答案，因?yàn)橛矌诺臄?shù)量是沒有限制的，子問題之間沒有相互制，是互相獨(dú)立的。

那么，既然知道了這是個(gè)動(dòng)態(tài)規(guī)劃問題，就要思考如何列出正確的狀態(tài)轉(zhuǎn)移方程。

先確定「狀態(tài)」，也就是原問題和子問題中變化的變量。由于硬幣數(shù)量無限，所以唯一的狀態(tài)就是目標(biāo)金額amount。

然后確定dp函數(shù)的定義：函數(shù)?dp(n)表示，當(dāng)前的目標(biāo)金額是n，至少需要dp(n)個(gè)硬幣湊出該金額。

然后確定「選擇」并擇優(yōu)，也就是對于每個(gè)狀態(tài)，可以做出什么選擇改變當(dāng)前狀態(tài)。具體到這個(gè)問題，無論當(dāng)?shù)哪繕?biāo)金額是多少，選擇就是從面額列表coins中選擇一個(gè)硬幣，然后目標(biāo)金額就會(huì)減少：

#?偽碼框架
def?coinChange(coins:?List[int],?amount:?int):
????#?定義：要湊出金額 n，至少要 dp(n)?個(gè)硬幣
????def?dp(n):
????????#?做選擇，需要硬幣最少的那個(gè)結(jié)果就是答案
????????for?coin?in?coins:
????????????res?=?min(res,?1?+?dp(n?-?coin))
????????return?res
????#?我們要求目標(biāo)金額是 amount
????return?dp(amount)

最后明確 base case，顯然目標(biāo)金額為 0 時(shí)，所需硬幣數(shù)量為 0；當(dāng)目標(biāo)金額小于 0 時(shí)，無解，返回 -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)移方程：

至此，這個(gè)問題其實(shí)就解決了，只不過需要消除一下重疊子問題，比如amount = 11, coins = {1,2,5}時(shí)畫出遞歸樹看看：

時(shí)間復(fù)雜度分析：子問題總數(shù) x 解決每個(gè)子問題的時(shí)間。

子問題總數(shù)為遞歸樹節(jié)點(diǎn)個(gè)數(shù)，這個(gè)比較難看出來，是 O(n^k)，總之是指數(shù)級別的。每個(gè)子問題中含有一個(gè) for 循環(huán)，復(fù)雜度為 O(k)。所以總時(shí)間復(fù)雜度為 O(k * n^k)，指數(shù)級別。

2、帶備忘錄的遞歸

只需要稍加修改，就可以通過備忘錄消除子問題：

def?coinChange(coins:?List[int],?amount:?int):
????#?備忘錄
????memo?=?dict()
????def?dp(n):
????????#?查備忘錄，避免重復(fù)計(jì)算
????????if?n?in?memo:?return?memo[n]

????????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ù)不會(huì)超過金額數(shù) n，即子問題數(shù)目為 O(n)。處理一個(gè)子問題的時(shí)間不變，仍是 O(k)，所以總的時(shí)間復(fù)雜度是 O(kn)。

3、dp 數(shù)組的迭代解法

當(dāng)然，我們也可以自底向上使用 dp table 來消除重疊子問題，dp數(shù)組的定義和剛才dp函數(shù)類似，定義也是一樣的：

dp[i] = x表示，當(dāng)目標(biāo)金額為i時(shí)，至少需要x枚硬幣。

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?(int?i?=?0;?i?????????//?內(nèi)層?for?在求所有子問題?+?1?的最小值
????????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)闇惓?code style="margin-right: 2px;margin-left: 2px;padding: 2px 4px;font-size: inherit;line-height: inherit;border-radius: 4px;color: rgb(233, 105, 0);background: rgb(248, 248, 248);">amount金額的硬幣數(shù)最多只可能等于amount（全用 1 元面值的硬幣），所以初始化為amount + 1就相當(dāng)于初始化為正無窮，便于后續(xù)取最小值。

三、最后總結(jié)

第一個(gè)斐波那契數(shù)列的問題，解釋了如何通過「備忘錄」或者「dp table」的方法來優(yōu)化遞歸樹，并且明確了這兩種方法本質(zhì)上是一樣的，只是自頂向下和自底向上的不同而已。

第二個(gè)湊零錢的問題，展示了如何流程化確定「狀態(tài)轉(zhuǎn)移方程」，只要通過狀態(tài)轉(zhuǎn)移方程寫出暴力遞歸解，剩下的也就是優(yōu)化遞歸樹，消除重疊子問題而已。

如果你不太了解動(dòng)態(tài)規(guī)劃，還能看到這里，真得給你鼓掌，相信你已經(jīng)掌握了這個(gè)算法的設(shè)計(jì)技巧。

計(jì)算機(jī)解決問題其實(shí)沒有任何奇技淫巧，它唯一的解決辦法就是窮舉，窮舉所有可能性。算法設(shè)計(jì)無非就是先思考“如何窮舉”，然后再追求“如何聰明地窮舉”。

列出動(dòng)態(tài)轉(zhuǎn)移方程，就是在解決“如何窮舉”的問題。之所以說它難，一是因?yàn)楹芏喔F舉需要遞歸實(shí)現(xiàn)，二是因?yàn)橛械膯栴}本身的解空間復(fù)雜，不那么容易窮舉完整。

備忘錄、DP table 就是在追求“如何聰明地窮舉”。用空間換時(shí)間的思路，是降低時(shí)間復(fù)雜度的不二法門，除此之外，試問，還能玩出啥花活？