斐波那契数
斐波那契数 序列有这样的公式： Fn = Fn-1 + Fn-2。换句话说，下一个数字是前两个数字的和。
前两个数字是 1，然后是 2(1+1)，然后 3(1+2)，5(2+3) 等：1, 1, 2, 3, 5, 8, 13, 21...。
斐波那契数与 黄金比例 以及我们周围的许多自然现象有关。
编写一个函数 fib(n) 返回第 n 个斐波那契数。
工作示例：
function fib(n) { /* 你的代码 */ }
alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757P.S. 函数运行速度要快，对 fib(77) 的调用不应该超过几分之一秒。
我们可以尝试的第一种解法是递归。
斐波那契数根据定义是递归的：
function fib(n) {
return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}
alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // 超级慢！……但是 n 比较大时会很慢。比如 fib(77) 会挂起引擎一段时间，并且消耗所有 CPU 资源。
因为函数产生了太多的子调用。同样的值被一遍又一遍地计算。
例如，我们看下计算 fib(5) 的片段：
...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...可以看到，fib(5) 和 fib(4) 都需要 fib(3) 的值，所以 fib(3) 被独立计算了两次。
这是完整的递归树：
我们可以清楚的看到 fib(3) 被计算了两次，fib(2) 被计算了三次。总计算量远远超过了 n，这造成仅仅对于计算 n=77 来讲，计算量就是巨量的。
我们可以通过记录已经计算过的值来进行优化：如果一个值比如 fib(3) 已经被计算过一次，那么我们可以在后面的计算中重复使用它。
另一个选择就是不使用递归，而是使用完全不同的基于循环的算法。
与从 n 到降到更小的值相反，我们可以使用循环从 1 和 2 开始，然后得到它们的和 fib(3)，然后再通过前两个数的和得到 fib(4)，然后 fib(5)，以此类推，直至达到所需要的值。在每一步，我们只需要记录前两个值就可以。
下面是新算法的细节步骤：
开始：
// a = fib(1), b = fib(2)，这些值是根据定义 1 得到的
let a = 1, b = 1;
// 求两者的和得到 c = fib(3)
let c = a + b;
/* 现在我们有 fib(1)，fib(2) 和 fib(3)
a b c
1, 1, 2
*/现在我们想要得到 fib(4) = fib(2) + fib(3)。
我们移动变量：a,b 将得到 fib(2),fib(3)，c 将得到两者的和：
a = b; // 现在 a = fib(2)
b = c; // 现在 b = fib(3)
c = a + b; // c = fib(4)
/* 现在我们有这样的序列
a b c
1, 1, 2, 3
*/下一步得到另一个序列数：
a = b; // 现在 a = fib(3)
b = c; // 现在 b = fib(4)
c = a + b; // c = fib(5)
/* 现在序列是（又加了一个数）：
a b c
1, 1, 2, 3, 5
*/……依次类推，直到我们得到需要的值。这比递归快很多，而且没有重复计算。
完整代码：
function fib(n) {
let a = 1;
let b = 1;
for (let i = 3; i <= n; i++) {
let c = a + b;
a = b;
b = c;
}
return b;
}
alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757循环从 i=3 开始，因为前两个序列值被硬编码到变量 a=1，b=1。
这种方式称为 自下而上的动态规划。