原文發(fā)表于公眾號 “l(fā)abuladong”啡浊，本文只是轉(zhuǎn)載猾昆，略有改動陶因，侵刪。
暴力遞歸
斐波那契數(shù)列的數(shù)學(xué)形式就是遞歸的垂蜗，如果寫成代碼就是：
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
代碼簡潔易懂楷扬，但是十分低效。低效在哪里贴见？假設(shè) n = 20烘苹，請畫出遞歸樹。
PS：但凡遇到需要遞歸的問題片部，最好都畫出遞歸樹镣衡，這樣有利于分析算法的復(fù)雜度，尋找算法低效的原因。
這個遞歸樹怎么理解廊鸥？就是說如果我們要計算f(20)望浩，就要先計算出子問題f(19)和f(18)，然后要計算f(19)黍图，就要先算出子問題f(18)和f(17)曾雕，以此類推。最后遇到f(2)或者是f(1)時助被，結(jié)果已知剖张，就可以直接返回結(jié)果，遞歸樹不再向下生長揩环。
遞歸算法的時間復(fù)雜度如何計算搔弄？子問題的個數(shù)乘以解決一個子問題需要的時間。
子問題的個數(shù)丰滑，即遞歸樹中節(jié)點的數(shù)量顾犹。顯然二叉樹的節(jié)點總數(shù)為指數(shù)級別，所以子問題的個數(shù)為 2^n褒墨。
解決一個子問題的時間炫刷，在本算法中，沒有循環(huán)郁妈，只有 f(n - 1) + f(n - 2) 一個加法操作浑玛，時間為O(1).
所以，這個算法的時間復(fù)雜度為 O(2^n)噩咪，指數(shù)級別顾彰。
觀察遞歸樹，很明顯發(fā)現(xiàn)了算法低效的原因：存在大量重復(fù)計算胃碾，比如f(18)被計算了兩次涨享，而且，以f(18)為根的這個遞歸樹體量巨大仆百，多算一遍厕隧，會耗費巨大的時間，更何況不止f(18)一個節(jié)點被重復(fù)計算儒旬，所以這個算法極其低效栏账。
這其實也是動態(tài)規(guī)劃問題中的第一個性質(zhì)：重復(fù)子問題。下面栈源，我們想辦法解決這個問題。
帶備忘錄的遞歸解法
既然耗時的原因是重復(fù)計算竖般，那么我們可以制造一個“備忘錄”甚垦，當然也可以使用哈希表（字典），思想都是一樣的。
public function fib($n)
{
if ($n < 1) {
return 0;
}
$hash = [];
return self::helper($hash, $n);
}
public static function helper(array &$hash, $n)
{
if($n == 1 || $n == 2) {
// base case
return 1;
}
if(isset($hash[$n]) && $hash[$n]) {
return $hash[$n];
}
$hash[$n] = self::helper($hash, $n - 1) + self::helper($hash, $n - 2);
return $hash[$n];
}
現(xiàn)在艰亮，畫出遞歸樹闭翩，你就知道“備忘錄”到底做了什么：
實際上，帶“備忘錄”的遞歸算法迄埃，把一顆存在巨量冗余的遞歸樹通過“剪枝”疗韵，改造成了一幅不存在冗余的遞歸圖，極大地減少了子問題（即遞歸圖中節(jié)點）的個數(shù)侄非。
遞歸算法的時間復(fù)雜度：子問題的個數(shù)乘以解決一個子問題需要的時間
子問題的個數(shù)為n蕉汪，解決一個子問題沒有循環(huán)，時間為O(1)逞怨。
所以者疤，本算法的時間復(fù)雜度是O(n)。
至此叠赦，帶備忘錄的遞歸解法的效率已經(jīng)和迭代的動態(tài)規(guī)劃一樣了驹马。實際上，這種解法和迭代的動態(tài)規(guī)劃思想已經(jīng)差不多除秀，只不過這種方法叫做“自頂向下”糯累，動態(tài)規(guī)劃叫做“自底向上”。
啥叫“自頂向下”册踩？注意到我們剛才花的遞歸樹泳姐，是從上向下延伸，都是從一個規(guī)模較大的問題比如
f(20)棍好，向下逐漸分解規(guī)模仗岸，直到f(1)和f(2)觸底，然后逐層返回答案借笙，這就叫“自頂向下”扒怖。
啥叫“自底向上”？ 反過來业稼，我們直接從最底下盗痒，最簡單，問題規(guī)模最小的f(1)和f(2)開始往上推低散，知道推到我們想要的答案f(20)俯邓，這就是動態(tài)規(guī)劃的思路，這也是為什么動態(tài)規(guī)劃一般都脫離了遞歸熔号，改為由循環(huán)迭代來完成計算稽鞭。
dp 數(shù)組的迭代解法
有了上一步“備忘錄”的啟發(fā)，我們可以把這個“備忘錄”獨立出來成為一張表引镊，就叫做DP table 吧朦蕴，在這張表上完成“自底向上”的推算篮条。
public function fibDp($n)
{
$hash = [];
$hash[1] = $hash[2] = 1;
for ($i = 3; $i <= $n; $i ++) {
$hash[$i] = $hash[$i-1] + $hash[$i-2];
}
return $hash[$n];
}
這個問題結(jié)構(gòu)的數(shù)據(jù)形式，就是：
一個細節(jié)優(yōu)化吩抓，根據(jù)斐波那契數(shù)列的狀態(tài)轉(zhuǎn)移方程涉茧，當前狀態(tài)只和之前的兩個狀態(tài)有關(guān)，其實并不需要那么長的一個DP table 來存儲所有的狀態(tài)疹娶，只需要想辦法存儲之前的兩個狀態(tài)即可伴栓。所以，算法可以進一步優(yōu)化雨饺，把空間復(fù)雜度也將為O(1)钳垮。
public function fib($n)
{
if($n == 1 || $n == 2) {
return 1;
}
$pre = $cur = 1;
for ($i = 3; $i <= $n; $i ++) {
$sum = $cur + $pre;
$pre = $cur;
$cur = $sum;
}
return $cur;
}
ps:該文章轉(zhuǎn)載于公眾號labuladong，侵刪沛膳。如果想了解學(xué)習(xí)關(guān)于算法的知識扔枫，請關(guān)注原作者 labuladong。
