斐波那契数列

题目描述

　　大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。

　　n<=39

---

实现代码

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)，这样看来，这一题只要两行代码就搞定了。

if (n<=1) return nelse return Fibonacci(n-1) + Fibonacci(n-2)

然而，测试用例中准备了一个超大的n来让Stack Overflow。

为什么会这样？因为重复的计算。举个例子：

Fibonacci(4) = Fibonacci(3) + Fibonacci(2);

　　　　　 = Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);

　　　　　= Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);

由于我们的代码并没有记录Fibonacci(1)和Fibonacci(0)的结果，对于程序来说它每次递归都是未知的，因此光是n=4时f(1)就重复计算了3次之多。

那么该如何求解呢？

以一定的空间代价来避免由重复计算造成的栈空间浪费。