Introduction
作為科班出身的程序員，算法還是得懂一點(diǎn)點(diǎn)的底循。------佚名(我)踱卵。
動(dòng)態(tài)規(guī)劃是一個(gè)看起來(lái)很高大上的名字，讓人一聽(tīng)就很想知道這到底是個(gè)啥郑临，所以我常常需要跟身邊好奇的朋友們解釋一下栖博。成功的讓朋友們理解了動(dòng)態(tài)規(guī)劃的基本思想后，我決定寫(xiě)一篇博客來(lái)幫助更多好奇的人??厢洞。
動(dòng)態(tài)規(guī)劃既是一種數(shù)學(xué)優(yōu)化方法仇让，也是一種計(jì)算機(jī)編程方法， 該方法由理查德·貝爾曼于20世紀(jì)50年代開(kāi)發(fā)躺翻，并已在航空航天工程和經(jīng)濟(jì)學(xué)等多個(gè)領(lǐng)域得到應(yīng)用丧叽。
本文將以計(jì)算斐波那契數(shù)和爬樓梯問(wèn)題為例，描述記憶化搜索及動(dòng)態(tài)規(guī)劃的基本思想公你，使讀者對(duì)動(dòng)態(tài)規(guī)劃有一個(gè)基本的理解踊淳。
Top-down Approach
斐波那契數(shù)列是一個(gè)人稱(chēng)“兔子數(shù)列”的數(shù)列，形如1陕靠，1迂尝，2，3剪芥，5垄开，......從數(shù)列的第n(n >= 3)個(gè)數(shù)開(kāi)始，第n個(gè)數(shù)的值為第n-1和第n-2個(gè)數(shù)的和税肪。由于斐波那契數(shù)列非常的簡(jiǎn)單直觀溉躲，它常被用作講解記憶化搜索思想的例子。
在一個(gè)斐波那契額數(shù)列中益兄，給定任意索引n, 如何求該位置的斐波那契數(shù)呢锻梳？最簡(jiǎn)單的方法，用遞歸：
private static int fibonacci(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
這個(gè)算法的時(shí)間復(fù)雜度是怎么樣的呢净捅，直觀的來(lái)看可能看不出來(lái)疑枯，如果將遞歸調(diào)用使用樹(shù)來(lái)進(jìn)行表示的話：
可以發(fā)現(xiàn)一共進(jìn)行了n層的調(diào)用，每往下走一層灸叼，節(jié)點(diǎn)數(shù)翻一倍(當(dāng)然這棵二叉樹(shù)不是滿的神汹，不論是國(guó)內(nèi)定義的還是國(guó)外定義的滿)，這表示這個(gè)算法的時(shí)間復(fù)雜度達(dá)到了指數(shù)級(jí)別古今。
仔細(xì)觀察遞歸樹(shù)我們可以發(fā)現(xiàn)屁魏，這棵樹(shù)中有很多重復(fù)的節(jié)點(diǎn)，或許我們可以使用緩存來(lái)減少遞歸調(diào)用捉腥，比如氓拼，使用某種數(shù)據(jù)結(jié)構(gòu)記錄n-2的值:
public class Main {
private static int[] memoryTable;
public static void main(String[] args) {
int n = 0;
memoryTable = new int[n + 1];
if (n >= 1) memoryTable[1] = 1;
if (n >= 2) memoryTable[2] = 1;
System.out.println("n's Fibonacci: " + fibonacci(n));
}
private static int fibonacci(int n) {
if (n <= 0) {
return -1;
}
if (memoryTable[n] == 0) {
memoryTable[n] = fibonacci(n - 1) + fibonacci(n - 2);
}
return memoryTable[n];
}
}
那么，根節(jié)點(diǎn)的右邊那個(gè)子樹(shù)就可以直接被省略掉，遞歸樹(shù)就變成了這樣：
使用一個(gè)大小為n + 1的數(shù)組來(lái)緩存計(jì)算過(guò)了的值犧牲了O(n)的空間(通常來(lái)說(shuō)完全可以接受)桃漾，算法被優(yōu)化到了線性時(shí)間復(fù)雜度坏匪。這種存儲(chǔ)已計(jì)算值的方法被稱(chēng)為“ memoization”。在Top-down approach里我們自頂向下的將一個(gè)問(wèn)題分解成子問(wèn)題并逐個(gè)求解撬统，通過(guò)記錄子問(wèn)題的解來(lái)進(jìn)行優(yōu)化适滓。
Bottom-up Approach
給定一個(gè)樓梯，你可以一次爬一階或者一次爬兩階恋追，但是每一次離開(kāi)第n階的時(shí)候需要花費(fèi)cost[n]的體力凭迹，求如何花費(fèi)最少的體力爬到頂，你可以從第一階或者第二階開(kāi)始網(wǎng)上爬苦囱。比如[30, 20, 60]嗅绸。花費(fèi)體力最少的方式就是從第二階往上爬一步撕彤，共耗費(fèi)20體力鱼鸠。通過(guò)舉例分析我們可以發(fā)現(xiàn)這個(gè)問(wèn)題有這樣的幾個(gè)特性：
1.該問(wèn)題最終的最優(yōu)解可以通過(guò)結(jié)合子問(wèn)題的最優(yōu)解來(lái)得到。在第n階的時(shí)候羹铅，我們只能從第n - 1階和第n - 2階爬上來(lái)蚀狰，所以我們只需要遞歸的求解爬到第n - 1階和第n - 2階最少需要多少步，然后取其中小的那一個(gè)就能得到爬到第n階最少需要多少步睦裳。
2.嘗試遞歸的求解的時(shí)候會(huì)發(fā)現(xiàn)我們會(huì)不斷的計(jì)算重復(fù)的子問(wèn)題造锅。從1我們可以看出來(lái)這個(gè)問(wèn)題的遞歸樹(shù)和求斐波那契數(shù)的問(wèn)題的遞歸樹(shù)是一樣的，所以我們可以跟之前一樣通過(guò)用一個(gè)數(shù)組來(lái)存儲(chǔ)已經(jīng)計(jì)算過(guò)的值來(lái)進(jìn)行優(yōu)化廉邑。
這個(gè)問(wèn)題的第一個(gè)特性叫做“Optimal substructure”，第二個(gè)特性叫做“Overlapping sub-problems”倒谷。同時(shí)具有這兩個(gè)特性的問(wèn)題才可能能夠通過(guò)動(dòng)態(tài)規(guī)劃來(lái)進(jìn)行求解蛛蒙。
通過(guò)以上分析，我們可以得出一個(gè)求解這個(gè)問(wèn)題的規(guī)律：
這個(gè)規(guī)律又叫狀態(tài)轉(zhuǎn)移方程渤愁，其中dp代表離開(kāi)某一階需要消耗的體力牵祟。
有了狀態(tài)轉(zhuǎn)移方程之后，我們其實(shí)可以不用寫(xiě)遞歸抖格，直接用遞推的方式從第一步推到第n步就可以得到結(jié)果:
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length];
for (int i = 0; i < cost.length; i++) {
if (i == 0 || i == 1) dp[i] = cost[i];
else dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
}
return Math.min(dp[dp.length - 1], dp[dp.length - 2]);
}
這種根據(jù)狀態(tài)轉(zhuǎn)移方程從最小的子問(wèn)題開(kāi)始一步一步推出最終結(jié)果的方式叫做Bottom-up Approach诺苹。
觀察代碼我們發(fā)現(xiàn)每一次我們?cè)谟?jì)算一個(gè)新的狀態(tài)的時(shí)候都只用前面兩個(gè)狀態(tài)，所以我們其實(shí)可以不用數(shù)組雹拄，直接用兩個(gè)變量記錄前兩個(gè)狀態(tài)的值就行了：
public int minCostClimbingStairs(int[] cost) {
int b = cost[1], c = cost[0];
for (int i = 2, a; i < cost.length; ++i, c=b, b = a) a = cost[i] + Math.min(b, c);
return Math.min(b, c);
}
我們發(fā)現(xiàn)Bottom-up Approach比Top-down Approach更進(jìn)一步收奔，把空間復(fù)雜度從O(n)優(yōu)化到了O(1)。
Conclusion and Prospect
本文通過(guò)兩個(gè)例子對(duì)動(dòng)態(tài)規(guī)劃的思想進(jìn)行了一個(gè)基本描述滓玖，重點(diǎn)描述了實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的Top-down Approach和Bottom-up Approach坪哄，針對(duì)具體問(wèn)題進(jìn)行了算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析。本文還講解了適合使用動(dòng)態(tài)規(guī)劃進(jìn)行解法優(yōu)化的問(wèn)題的特性。
動(dòng)態(tài)規(guī)劃的應(yīng)用非常廣泛翩肌，而且具體問(wèn)題可能會(huì)比較復(fù)雜模暗，希望熟練掌握的同學(xué)可以去各大OJ找題自虐一下??。懶得找的同學(xué)可以直接試一下這道谷歌的面試題念祭。
References
[1] Dynamic programming的維基百科
[2]Min Cost Climbing Stairs
Acknowledgments
感謝那些在看到我讀算法書(shū)的時(shí)候跑過(guò)來(lái)問(wèn)我你懂動(dòng)態(tài)規(guī)劃嗎或者是在聽(tīng)說(shuō)動(dòng)態(tài)規(guī)劃后忍不住要刨根問(wèn)底的好奇寶寶們兑宇，是你們引發(fā)了我的思考。
