斐波那契數(shù)列
題目描述
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)靴姿。
n<=39
實(shí)現(xiàn)代碼
function Fibonacci(n)
{
var arr = [];
arr[0] = 0;
arr[1] = 1;
for(var i = 2; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
思路
看到題目，首先想到的就是遞歸磁滚，f(n) = f(n-1) + f(n-2)佛吓，這樣看來(lái)，這一題只要兩行代碼就搞定了垂攘。
if (n<=1) return n
else return Fibonacci(n-1) + Fibonacci(n-2)
然而维雇，測(cè)試用例中準(zhǔn)備了一個(gè)超大的n來(lái)讓Stack Overflow。
Z31~F09BCFQ@R$N8T[2]4XJ.png
為什么會(huì)這樣晒他？因?yàn)橹貜?fù)的計(jì)算吱型。舉個(gè)例子：
Fibonacci(4) = Fibonacci(3) + Fibonacci(2);
= Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
= Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
由于我們的代碼并沒(méi)有記錄Fibonacci(1)和Fibonacci(0)的結(jié)果，對(duì)于程序來(lái)說(shuō)它每次遞歸都是未知的陨仅，因此光是n=4時(shí)f(1)就重復(fù)計(jì)算了3次之多津滞。
那么該如何求解呢？
以一定的空間代價(jià)來(lái)避免由重復(fù)計(jì)算造成的椬粕耍空間浪費(fèi)触徐。
