斐波那契数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数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 n
else return Fibonacci(n-1) + Fibonacci(n-2)
然而，测试用例中准备了一个超大的n来让Stack Overflow。
Z31~F09BCFQ@R$N8T[2]4XJ.png
为什么会这样？因为重复的计算。举个例子：
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次之多。
那么该如何求解呢？
以一定的空间代价来避免由重复计算造成的栈空间浪费。
