大名鼎鼎的斐波那契數(shù)列：0，1谣拣，1募寨，2，3森缠，5，8仪缸，13贵涵，21......使用數(shù)學歸納法可以看出其規(guī)律為：f(n) = f(n-1) + f(n-2)。
遞歸
下面首先直接使用遞歸（JavaScript實現(xiàn)）來求解第 n 項：f(n)
// 直接使用遞歸
let num = 0; // 用來記錄fib函數(shù)執(zhí)行次數(shù)，執(zhí)行一次加一
function fib(n) {
num ++;
if(n === 0) {
return 0;
}
if(n === 1) {
return 1;
}
return fib(n-1) + fib(n-2);
}
console.time("time used");
console.log(`result is: ${fib(40)}`);
console.log(`fib() runned ${num} times`);
console.timeEnd("time used");
以 n = 40 為例宾茂，這里我們記錄了 fib 函數(shù)總共調(diào)用的次數(shù)以及運算總共耗時瓷马，結果如下：
可以看出，即便僅僅是計算第 40 項跨晴，fib 函數(shù)調(diào)用的次數(shù)高達3億多次欧聘，時間是2477ms。因為每一次 fib 函數(shù)的調(diào)用都會有兩個子 fib 函數(shù)調(diào)用端盆，那么時間復雜度是 O(2^n) 怀骤，呈指數(shù)級增長，這顯然不是一個好算法焕妙。怎么優(yōu)化呢蒋伦？以一個簡單的例子畫圖分析一下：
上圖是 n = 5 時的遞歸樹，可以看出虛線框中 f(2) 的計算用到了三次焚鹊，同樣的 f(3) 的計算用到了兩次痕届，顯然我們執(zhí)行了非常多的重復運算。那么很自然的想到末患，把每一個狀態(tài)的計算結果都存起來研叫，后面遇到相同的狀態(tài)就可以直接使用了。
記憶化搜索遞歸(自頂向下)
代碼如下璧针，這里第三行 new 了一個長度為 n+1 的數(shù)組蓝撇，用于存放 f(0) 到 f(n) 這 n+1 個狀態(tài)的計算結果：
// 記憶化搜索，記錄每次計算的結果
let num = 0; // 用來記錄fib函數(shù)執(zhí)行次數(shù)陈莽，執(zhí)行一次加一
let totalnum = 40;
let memory = new Array(totalnum+1).fill(-1);
function fib(n) {
num++;
if(n === 0) {
return 0;
}
if(n === 1) {
return 1;
}
if(memory[n] === -1) {
memory[n] = fib(n-1) + fib(n-2); // 如果前面已經(jīng)得到渤昌，直接使用
}
return memory[n];
}
console.time("timer");
console.log(`result is: ${fib(totalnum)}`);
console.log(`fib() runned ${num} times`);
console.timeEnd("timer");
同樣 n = 40，結果如下：
可以看處出優(yōu)化是十分可觀的走搁，記錄下每一次子調(diào)用的結果独柑，讓算法復雜度從 O(2^n) 變成了 O(n)。這其實就是動態(tài)規(guī)劃的思想私植。什么是動態(tài)規(guī)劃忌栅？
Dynamic programming is when you use past knowledge to make solving a future problem easier.(動態(tài)規(guī)劃是用已知項去更好的求解未知項)
Dynamic programming is a technique used to avoid computing multiple time the same subproblem in a recursive algorithm.
將原問題拆解成若干子問題，同時保存子問題的答案曲稼，使得每個子問題只求解一次索绪，最終獲得原問題的答案。
以上是我看到的兩個很好的定義贫悄。記憶化搜索遞歸求斐波那契數(shù)列顯然是使用了動態(tài)規(guī)劃的思想瑞驱，并且，這是一種自頂向下的求解方式（我們沒有從最基本的問題開始求解窄坦，對于 f(n) = f(n-1) + f(n-2) 唤反，先假定 f(n-1) 和 f(n-2) 是已知的）凳寺。另外我們可以采用另一種自下向上的方式求解，即迭代彤侍，這也是一種動態(tài)規(guī)劃的思想肠缨。
迭代法(自下向上)
代碼如下，我們使用迭代盏阶，f(2) = f(1) + f(0)晒奕，f(3) = f(2) + f(1)，.....名斟，顯然這是一種從基礎問題開始的自下向上的解決方法：
let num = 0;
function fib(n) {
num++;
let memory = new Array(n+1);
memory[0] = 1;
memory[1] = 1;
for(let i = 2; i <= n; i++) {
memory[i] = memory[i-1] + memory[i-2];
}
return memory[n];
}
console.time("timer");
console.log(`result is: ${fib(40)}`);
console.log(`fib() runned ${num} times`);
console.timeEnd("timer");
結果如下脑慧，顯然使用迭代的方法復雜度也為 O(n)：
小結
動態(tài)規(guī)劃就是：將原問題拆解成若干子問題，同時保存子問題的答案，使得每個子問題只求解一次，最終獲得原問題的答案稚配。對于斐波那契數(shù)列的求解，有自頂向下的記憶化搜索遞歸和自下向上的迭代法霜运，他們都使用了動態(tài)規(guī)劃的思想。
參考鏈接：
https://stackoverflow.com/questions/1065433/what-is-dynamic-programming
