共计 1249 个字符，预计需要花费 4 分钟才能阅读完成。
题目
题目描述大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）。
基本思路
这道题在剑指 offer 中实际是当作递归的反例来说的。
递归的本质是吧一个问题分解成两个或者多个小问题，如果多个小问题存在互相重叠的情况，那么就存在重复计算。
f(n) = f(n-1) + f(n-2) 这种拆分使用递归是典型的存在重叠的情况，所以会造成非常多的重复计算。
另外，每一次函数调用爱内存中都需要分配空间，每个进程的栈的容量是有限的，递归层次过多，就会造成栈溢出。
递归是从最大数开始，不断拆解成小的数计算，如果不去考虑递归，我们只需要从小数开始算起，从底层不断往上累加就可以了，其实思路也很简单。
代码
function Fibonacci(n)
{
if(n<=1){
return n;
}
let i = 1;
let pre = 0;
let current = 1;
let result = 0;
while(i++ < n){
result = pre + current;
pre = current;
current = result;
}
return result;
}
扩展
1. 跳台阶：
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
找规律：
跳三级台阶等于跳两级台阶的跳法 + 跳一级台阶的跳法。
跳四级台阶等于跳三级台阶的跳法 + 跳二级台阶的跳法。
明显也符合斐波那契数列的规律
function jumpFloor(n)
{
if(n<=2){
return n;
}
let i = 2;
let pre = 1;
let current = 2;
let result = 0;
while(i++ < n){
result = pre + current;
pre = current;
current = result;
}
return result;
}
3. 矩形覆盖
我们可以用 21 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 21 的小矩形无重叠地覆盖一个 2 * n 的大矩形，总共有多少种方法？
跟上面跳台阶那个题很像。
假设有 8 个块
第 1 块竖着放，后面还剩 7 块，共 f(7) 种方法。
第 1 块横着放，后面还剩 6 块，共 f(6) 种方法。
即 f(8)=f(6)+f(7)
f(n)=f(n-1)+f(n-2)
function rectCover(n)
{
if(n<=2){
return n;
}
let i = 2;
let pre = 1;
let current = 2;
let result = 0;
while(i++ < n){
result = pre + current;
pre = current;
current = result;
}
return result;
}
3. 变态跳台阶
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级……它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
每个台阶都可以选择跳或者不跳，最后一个台阶必跳。
每个台阶有两种选择，n 个台阶有 2 的 n 次方种选择。
所以一共有 2 的 n - 1 次跳法。
使用位运算
function jumpFloorII(number)
{
return 1<<(–number);
}
