在學(xué)習(xí)「數(shù)據(jù)結(jié)構(gòu)和算法」的過程中，因?yàn)槿肆?xí)慣了平鋪直敘的思維方式，所以「遞歸」與「動(dòng)態(tài)規(guī)劃」這種帶循環(huán)概念（繞來(lái)繞去）的往往是相對(duì)比較難以理解的兩個(gè)抽象知識(shí)點(diǎn)。
程序員小吳打算使用動(dòng)畫的形式來(lái)幫助理解「遞歸」于样，然后通過「遞歸」的概念延伸至理解「動(dòng)態(tài)規(guī)劃」算法思想。
什么是遞歸
先下定義：遞歸算法是一種直接或者間接調(diào)用自身函數(shù)或者方法的算法潘靖。
通俗來(lái)說穿剖，遞歸算法的實(shí)質(zhì)是把問題分解成規(guī)模縮小的同類問題的子問題卦溢，然后遞歸調(diào)用方法來(lái)表示問題的解糊余。它有如下特點(diǎn)：
- 一個(gè)問題的解可以分解為幾個(gè)子問題的解
- 這個(gè)問題與分解之后的子問題，除了數(shù)據(jù)規(guī)模不同单寂，求解思路完全一樣
- 存在遞歸終止條件贬芥，即必須有一個(gè)明確的遞歸結(jié)束條件，稱之為遞歸出口
通過動(dòng)畫一個(gè)一個(gè)特點(diǎn)來(lái)進(jìn)行分析宣决。
1.一個(gè)問題的解可以分解為幾個(gè)子問題的解
子問題就是相對(duì)與其前面的問題數(shù)據(jù)規(guī)模更小的問題蘸劈。
在動(dòng)圖中①號(hào)問題（一塊大區(qū)域）劃分為②號(hào)問題，②號(hào)問題由兩個(gè)子問題（兩塊中區(qū)域）組成尊沸。
2. 這個(gè)問題與分解之后的子問題昵时，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
「①號(hào)劃分為②號(hào)」與「②號(hào)劃分為③號(hào)」的邏輯是一致的椒丧，求解思路是一樣的壹甥。
3. 存在遞歸終止條件，即存在遞歸出口
把問題分解為子問題壶熏，把子問題再分解為子子問題句柠，一層一層分解下去，不能存在無(wú)限循環(huán)棒假，這就需要有終止條件溯职。
①號(hào)劃分為②號(hào)，②號(hào)劃分為③號(hào)帽哑，③號(hào)劃分為④號(hào)谜酒，劃分到④號(hào)的時(shí)候每個(gè)區(qū)域只有一個(gè)不能劃分的問題，這就表明存在遞歸終止條件妻枕。
從遞歸的經(jīng)典示例開始
一.數(shù)組求和
Sum(arr[0...n-1]) = arr[0] + Sum(arr[1...n-1])
后面的 Sum 函數(shù)要解決的就是比前一個(gè) Sum 更小的同一問題僻族。
Sum(arr[1...n-1]) = arr[1] + Sum(arr[2...n-1])
以此類推粘驰，直到對(duì)一個(gè)空數(shù)組求和，空數(shù)組和為 0 述么，此時(shí)變成了最基本的問題蝌数。
Sum(arr[n-1...n-1] ) = arr[n-1] + Sum([])
二.漢諾塔問題
漢諾塔（Hanoi Tower）問題也是一個(gè)經(jīng)典的遞歸問題，該問題描述如下：
漢諾塔問題：古代有一個(gè)梵塔度秘，塔內(nèi)有三個(gè)座A顶伞、B、C剑梳，A座上有64個(gè)盤子唆貌，盤子大小不等，大的在下垢乙，小的在上锨咙。有一個(gè)和尚想把這個(gè)盤子從A座移到B座，但每次只能允許移動(dòng)一個(gè)盤子侨赡，并且在移動(dòng)過程中蓖租，3個(gè)座上的盤子始終保持大盤在下，小盤在上羊壹。
① 如果只有 1 個(gè)盤子蓖宦，則不需要利用 B 塔，直接將盤子從 A 移動(dòng)到 C 油猫。
② 如果有 2 個(gè)盤子稠茂，可以先將盤子 2 上的盤子 1 移動(dòng)到 B ；將盤子 2 移動(dòng)到 C 情妖；將盤子 1 移動(dòng)到 C 睬关。這說明了：可以借助 B 將 2 個(gè)盤子從 A 移動(dòng)到 C ，當(dāng)然毡证，也可以借助 C 將 2 個(gè)盤子從 A 移動(dòng)到 B 电爹。
③ 如果有 3 個(gè)盤子，那么根據(jù) 2 個(gè)盤子的結(jié)論料睛，可以借助 C 將盤子 3 上的兩個(gè)盤子從 A 移動(dòng)到 B 丐箩；將盤子 3 從 A 移動(dòng)到 C ，A 變成空座恤煞；借助 A 座屎勘，將 B 上的兩個(gè)盤子移動(dòng)到 C 。
④ 以此類推居扒，上述的思路可以一直擴(kuò)展到 n 個(gè)盤子的情況概漱，將將較小的 n-1個(gè)盤子看做一個(gè)整體，也就是我們要求的子問題喜喂，以借助 B 塔為例瓤摧，可以借助空塔 B 將盤子A上面的 n-1 個(gè)盤子從 A 移動(dòng)到 B 竿裂；將A 最大的盤子移動(dòng)到 C ， A 變成空塔姻灶；借助空塔 A 铛绰，將 B 塔上的 n-2 個(gè)盤子移動(dòng)到 A诈茧，將 C 最大的盤子移動(dòng)到 C产喉， B 變成空塔。敢会。曾沈。
三.爬臺(tái)階問題
問題描述：
一個(gè)人爬樓梯，每次只能爬1個(gè)或2個(gè)臺(tái)階鸥昏，假設(shè)有n個(gè)臺(tái)階塞俱，那么這個(gè)人有多少種不同的爬樓梯方法？
先從簡(jiǎn)單的開始吏垮，以 4 個(gè)臺(tái)階為例障涯，可以通過每次爬 1 個(gè)臺(tái)階爬完樓梯：
可以通過先爬 2 個(gè)臺(tái)階，剩下的每次爬 1 個(gè)臺(tái)階爬完樓梯
在這里膳汪，可以思考一下：可以根據(jù)第一步的走法把所有走法分為兩類：
- ① 第一類是第一步走了 1 個(gè)臺(tái)階
- ② 第二類是第一步走了 2 個(gè)臺(tái)階
所以 n 個(gè)臺(tái)階的走法就等于先走 1 階后唯蝶，n-1 個(gè)臺(tái)階的走法 ，然后加上先走 2 階后遗嗽，n-2 個(gè)臺(tái)階的走法粘我。
用公式表示就是：
f(n) = f(n-1)+f(n-2)
有了遞推公式，遞歸代碼基本上就完成了一半痹换。那么接下來(lái)考慮遞歸終止條件征字。
當(dāng)有一個(gè)臺(tái)階時(shí)，我們不需要再繼續(xù)遞歸娇豫，就只有一種走法匙姜。
所以 f(1)=1。
通過用 n = 2冯痢，n = 3 這樣比較小的數(shù)試驗(yàn)一下后發(fā)現(xiàn)這個(gè)遞歸終止條件還不足夠氮昧。
n = 2 時(shí)，f(2) = f(1) + f(0)系羞。如果遞歸終止條件只有一個(gè)f(1) = 1郭计，那 f(2) 就無(wú)法求解，遞歸無(wú)法結(jié)束椒振。
所以除了 f(1) = 1 這一個(gè)遞歸終止條件外昭伸，還要有 f(0) = 1，表示走 0 個(gè)臺(tái)階有一種走法澎迎，從思維上以及動(dòng)圖上來(lái)看庐杨，這顯得的有點(diǎn)不符合邏輯选调。所以為了便于理解，把 f(2) = 2 作為一種終止條件灵份，表示走 2 個(gè)臺(tái)階仁堪，有兩種走法，一步走完或者分兩步來(lái)走填渠。
總結(jié)如下：
- ① 假設(shè)只有一個(gè)臺(tái)階弦聂，那么只有一種走法，那就是爬 1 個(gè)臺(tái)階
- ② 假設(shè)有兩個(gè)個(gè)臺(tái)階氛什，那么有兩種走法莺葫，一步走完或者分兩步來(lái)走
通過遞歸條件：
f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2)
很容易推導(dǎo)出遞歸代碼：
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}
通過上述三個(gè)示例，總結(jié)一下如何寫遞歸代碼：
- 1.找到如何將大問題分解為小問題的規(guī)律
- 2.通過規(guī)律寫出遞推公式
- 3.通過遞歸公式的臨界點(diǎn)推敲出終止條件
- 4.將遞推公式和終止條件翻譯成代碼
什么是動(dòng)態(tài)規(guī)劃
介紹動(dòng)態(tài)規(guī)劃之前先介紹一下分治策略（Divide and Conquer）枪眉。
分治策略
將原問題分解為若干個(gè)規(guī)模較小但類似于原問題的子問題（Divide）捺檬，「遞歸」的求解這些子問題（Conquer），然后再合并這些子問題的解來(lái)建立原問題的解贸铜。
因?yàn)樵谇蠼獯髥栴}時(shí)堡纬，需要遞歸的求小問題，因此一般用「遞歸」的方法實(shí)現(xiàn)蒿秦，即自頂向下烤镐。
動(dòng)態(tài)規(guī)劃（Dynamic Programming）
動(dòng)態(tài)規(guī)劃其實(shí)和分治策略是類似的，也是將一個(gè)原問題分解為若干個(gè)規(guī)模較小的子問題渤早，遞歸的求解這些子問題职车，然后合并子問題的解得到原問題的解。
區(qū)別在于這些子問題會(huì)有重疊鹊杖，一個(gè)子問題在求解后悴灵，可能會(huì)再次求解，于是我們想到將這些子問題的解存儲(chǔ)起來(lái)骂蓖，當(dāng)下次再次求解這個(gè)子問題時(shí)积瞒，直接拿過來(lái)就是。
其實(shí)就是說登下，動(dòng)態(tài)規(guī)劃所解決的問題是分治策略所解決問題的一個(gè)子集茫孔，只是這個(gè)子集更適合用動(dòng)態(tài)規(guī)劃來(lái)解決從而得到更小的運(yùn)行時(shí)間。
即用動(dòng)態(tài)規(guī)劃能解決的問題分治策略肯定能解決被芳，只是運(yùn)行時(shí)間長(zhǎng)了嵌牺。因此卖丸，分治策略一般用來(lái)解決子問題相互對(duì)立的問題柒傻，稱為標(biāo)準(zhǔn)分治晶乔，而動(dòng)態(tài)規(guī)劃用來(lái)解決子問題重疊的問題。
與「分治策略」「動(dòng)態(tài)規(guī)劃」概念接近的還有「貪心算法」「回溯算法」，由于篇幅限制赞弥，程序員小吳就不在這進(jìn)行展開毅整，在后續(xù)的文章中將分別詳細(xì)的介紹「貪心算法」、「回溯算法」绽左、「分治算法」悼嫉，敬請(qǐng)關(guān)注：）
將「動(dòng)態(tài)規(guī)劃」的概念關(guān)鍵點(diǎn)抽離出來(lái)描述就是這樣的：
- 1.動(dòng)態(tài)規(guī)劃法試圖只解決每個(gè)子問題一次
- 2.一旦某個(gè)給定子問題的解已經(jīng)算出，則將其記憶化存儲(chǔ)拼窥，以便下次需要同一個(gè)子問題解之時(shí)直接查表戏蔑。
從遞歸到動(dòng)態(tài)規(guī)劃
還是以 爬臺(tái)階 為例，如果以遞歸的方式解決的話闯团，那么這種方法的時(shí)間復(fù)雜度為O(2^n)辛臊，具體的計(jì)算可以查看筆者之前的文章 《冰與火之歌：時(shí)間復(fù)雜度與空間復(fù)雜度》仙粱。
相同顏色代表著 爬臺(tái)階問題 在遞歸計(jì)算過程中重復(fù)計(jì)算的部分房交。
通過圖片可以發(fā)現(xiàn)一個(gè)現(xiàn)象，我們是 自頂向下 的進(jìn)行遞歸運(yùn)算伐割，比如：f(n) 是f(n-1)與f(n-2)相加候味，f(n-1) 是f(n-2)與f(n-3)相加。
思考一下：如果反過來(lái)隔心，采取自底向上白群，用迭代的方式進(jìn)行推導(dǎo)會(huì)怎么樣了？
下面通過表格來(lái)解釋 f(n)自底向上的求解過程硬霍。
| 臺(tái)階數(shù) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 走法數(shù) | 1 | 2 |
表格的第一行代表了樓梯臺(tái)階的數(shù)目帜慢，第二行代表了若干臺(tái)階對(duì)應(yīng)的走法數(shù)。
其中f(1) = 1 和 f(2) = 2是前面明確的結(jié)果唯卖。
第一次迭代粱玲，如果臺(tái)階數(shù)為 3 ，那么走法數(shù)為 3 拜轨，通過 f(3) = f(2) + f(1)得來(lái)抽减。
| 臺(tái)階數(shù) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 走法數(shù) | 1 | 2 | 3 |
第二次迭代，如果臺(tái)階數(shù)為 4 橄碾，那么走法數(shù)為 5 卵沉，通過 f(4) = f(3) + f(2)得來(lái)。
| 臺(tái)階數(shù) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 走法數(shù) | 1 | 2 | 3 | 5 |
由此可見法牲，每一次迭代過程中史汗，只需要保留之前的兩個(gè)狀態(tài)，就可以推到出新的狀態(tài)拒垃。
show me the code
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
// a 保存倒數(shù)第二個(gè)子狀態(tài)數(shù)據(jù)停撞，b 保存倒數(shù)第一個(gè)子狀態(tài)數(shù)據(jù)， temp 保存當(dāng)前狀態(tài)的數(shù)據(jù)
int a = 1, b = 2;
int temp = a + b;
for (int i = 3; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return temp;
}
程序從 i = 3 開始迭代恶复，一直到 i = n 結(jié)束怜森。每一次迭代速挑，都會(huì)計(jì)算出多一級(jí)臺(tái)階的走法數(shù)量。迭代過程中只需保留兩個(gè)臨時(shí)變量 a 和 b 副硅，分別代表了上一次和上上次迭代的結(jié)果姥宝。為了便于理解，引入了temp變量恐疲。temp代表了當(dāng)前迭代的結(jié)果值腊满。
看一看出，事實(shí)上并沒有增加太多的代碼培己，只是簡(jiǎn)單的進(jìn)行了優(yōu)化碳蛋，時(shí)間復(fù)雜度便就降為O(n)，而空間復(fù)雜度也變?yōu)镺(1)省咨，這肃弟，就是「動(dòng)態(tài)規(guī)劃」的強(qiáng)大！
詳解動(dòng)態(tài)規(guī)劃
「動(dòng)態(tài)規(guī)劃」中包含三個(gè)重要的概念：
- 【最優(yōu)子結(jié)構(gòu)】
- 【邊界】
- 【狀態(tài)轉(zhuǎn)移公式】
在「 爬臺(tái)階問題 」中
f(10) = f(9) + f(8)是【最優(yōu)子結(jié)構(gòu)】
f(1) 與 f(2)是【邊界】
f(n) = f(n-1) + f(n-2)【狀態(tài)轉(zhuǎn)移公式】
「 爬臺(tái)階問題 」 只是動(dòng)態(tài)規(guī)劃中相對(duì)簡(jiǎn)單的問題零蓉，因?yàn)樗挥幸粋€(gè)變化維度笤受，如果涉及多個(gè)維度的話，那么問題就變得復(fù)雜多了敌蜂。
難點(diǎn)就在于找出 「動(dòng)態(tài)規(guī)劃」中的這三個(gè)概念箩兽。
比如「 國(guó)王和金礦問題 」。
國(guó)王和金礦問題
有一個(gè)國(guó)家發(fā)現(xiàn)了 5 座金礦章喉，每座金礦的黃金儲(chǔ)量不同汗贫，需要參與挖掘的工人數(shù)也不同。參與挖礦工人的總數(shù)是 10 人秸脱。每座金礦要么全挖落包，要么不挖，不能派出一半人挖取一半金礦撞反。要求用程序求解出妥色，要想得到盡可能多的黃金，應(yīng)該選擇挖取哪幾座金礦遏片？
5 座金礦
找出 「動(dòng)態(tài)規(guī)劃」中的這三個(gè)概念
國(guó)王和金礦問題中的【最優(yōu)子結(jié)構(gòu)】
國(guó)王和金礦問題中的【最優(yōu)子結(jié)構(gòu)】有兩個(gè)：
- ① 4 金礦 10 工人的最優(yōu)選擇
- ② 4 金礦 （10 - 5） 工人的最優(yōu)選擇
4 金礦的最優(yōu)選擇與 5 金礦的最優(yōu)選擇之間的關(guān)系是
MAX[（4 金礦 10 工人的挖金數(shù)量）嘹害，（4 金礦 5 工人的挖金數(shù)量 + 第 5 座金礦的挖金數(shù)量）]
國(guó)王和金礦問題中的【邊界】
國(guó)王和金礦問題中的【邊界】 有兩個(gè)：
- ① 當(dāng)只有 1 座金礦時(shí)，只能挖這座唯一的金礦吮便，得到的黃金數(shù)量為該金礦的數(shù)量
- ② 當(dāng)給定的工人數(shù)量不夠挖 1 座金礦時(shí)笔呀，獲取的黃金數(shù)量為 0
國(guó)王和金礦問題中的【狀態(tài)轉(zhuǎn)移公式】
我們把金礦數(shù)量設(shè)為 N，工人數(shù)設(shè)為 W髓需，金礦的黃金量設(shè)為數(shù)組G[]许师，金礦的用工量設(shè)為數(shù)組P[]，得到【狀態(tài)轉(zhuǎn)移公式】：
?
邊界值：F(n,w) = 0 (n <= 1, w < p[0])
F(n,w) = g[0] (n==1, w >= p[0])F(n,w) = F(n-1,w) (n > 1, w < p[n-1])
F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1]) + g[n-1]) (n > 1, w >= p[n-1])
國(guó)王和金礦問題中的【實(shí)現(xiàn)】
先通過幾幅動(dòng)畫來(lái)理解 「工人」 與 「金礦」 搭配的方式
1.只挖第一座金礦
在只挖第一座金礦前面兩個(gè)工人挖礦收益為 零，當(dāng)有三個(gè)工人時(shí)微渠，才開始產(chǎn)生收益為 200搭幻，而后即使增加再多的工人收益不變，因?yàn)橹挥幸蛔鸬V可挖逞盆。
2.挖第一座與第二座金礦
在第一座與第二座金礦這種情況中檀蹋，前面兩個(gè)工人挖礦收益為 零，因?yàn)?W < 3,所以F(N,W) = F(N-1,W) = 0云芦。
當(dāng)有 三 個(gè)工人時(shí)俯逾，將其安排挖第 一 個(gè)金礦，開始產(chǎn)生收益為 200舅逸。
當(dāng)有 四 個(gè)工人時(shí)桌肴，挖礦位置變化，將其安排挖第 二 個(gè)金礦琉历，開始產(chǎn)生收益為 300坠七。
當(dāng)有 五、六 個(gè)工人時(shí)善已，由于多于 四 個(gè)工人的人數(shù)不足以去開挖第 一 座礦灼捂，因此收益還是為 300。
當(dāng)有 七 個(gè)工人時(shí)换团，可以同時(shí)開采第 一 個(gè)和第 二 個(gè)金礦，開始產(chǎn)生收益為 500宫蛆。
3.挖前三座金礦
這是「國(guó)王和金礦」 問題中最重要的一個(gè)動(dòng)畫之一艘包，可以多看幾遍
4.挖前四座金礦
這是「國(guó)王和金礦」 問題中最重要的一個(gè)動(dòng)畫之一，可以多看幾遍
國(guó)王和金礦問題中的【規(guī)律】
仔細(xì)觀察上面的幾組動(dòng)畫可以發(fā)現(xiàn)：
對(duì)比「挖第一座與第二座金礦」和「挖前三座金礦」耀盗，在「挖前三座金礦」中想虎，3 金礦 7 工人的挖礦收益，來(lái)自于 2 金礦 7 工人和 2 金礦 4 工人的結(jié)果叛拷，Max(500,300 + 350) = 650舌厨；
對(duì)比「挖前三座金礦」和「挖前四座金礦」，在「挖前四座金礦」中忿薇，4 金礦 10 工人的挖礦收益裙椭，來(lái)自于 3 金礦 10 工人和 3 金礦 5 工人的結(jié)果，Max(850,400 + 300) = 850署浩；
國(guó)王和金礦問題中的【動(dòng)態(tài)規(guī)劃代碼】
代碼來(lái)源：https://www.cnblogs.com/SDJL/archive/2008/08/22/1274312.html
//maxGold[i][j] 保存了i個(gè)人挖前j個(gè)金礦能夠得到的最大金子數(shù)揉燃，等于 -1 時(shí)表示未知
int maxGold[max_people][max_n];
int GetMaxGold(int people, int mineNum){
int retMaxGold; //聲明返回的最大金礦數(shù)量
//如果這個(gè)問題曾經(jīng)計(jì)算過
if(maxGold[people][mineNum] != -1){
retMaxGold = maxGold[people][mineNum]; //獲得保存起來(lái)的值
}else if(mineNum == 0) { //如果僅有一個(gè)金礦時(shí) [ 對(duì)應(yīng)動(dòng)態(tài)規(guī)劃中的"邊界"]
if(people >= peopleNeed[mineNum]) //當(dāng)給出的人數(shù)足夠開采這座金礦
retMaxGold = gold[mineNum]; //得到的最大值就是這座金礦的金子數(shù)
else //否則這唯一的一座金礦也不能開采
retMaxGold = 0; //得到的最大值為 0 個(gè)金子
}else if(people >= peopleNeed[mineNum]) // 如果人夠開采這座金礦[對(duì)應(yīng)動(dòng)態(tài)規(guī)劃中的"最優(yōu)子結(jié)構(gòu)"]
{
//考慮開采與不開采兩種情況，取最大值
retMaxGold = max(
GetMaxGold(people - peopleNeed[mineNum],mineNum - 1) + gold[mineNum],
GetMaxGold(people,mineNum - 1)
);
}else//否則給出的人不夠開采這座金礦 [ 對(duì)應(yīng)動(dòng)態(tài)規(guī)劃中的"最優(yōu)子結(jié)構(gòu)"]
{
retMaxGold = GetMaxGold(people,mineNum - 1); //僅考慮不開采的情況
maxGold[people][mineNum] = retMaxGold;
}
return retMaxGold;
}
希望通過這篇文章筋栋，大家能對(duì)「遞歸」與「動(dòng)態(tài)規(guī)劃」有一定的理解炊汤。后續(xù)將以「動(dòng)態(tài)規(guī)劃」為基礎(chǔ)研究多重背包算法、迪杰特斯拉算法等更高深的算法問題，同時(shí)「遞歸」的更多概念也會(huì)在「分治算法」章節(jié)再次延伸抢腐，敬請(qǐng)對(duì)程序員小吳保持關(guān)注：）
