算法：青蛙跳台阶和斐波那契数列

简单

一次跳一层或两层，求跳上一个n级的台阶总共有多少种跳法。
因为n级台阶，第一步有n种跳法：跳1级、跳2级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)

f(0)=0
f(1)=1
f(2)=2
f(n)=f(n-1)+f(n-2)

function jump(n){
    if(n==0){
        return 0;
    }else if(n==1){
        return 1;
    }else if(n==2){
        return 2;
    }else{
        return jump(n-1)+jump(n-2);
    }
}

复杂

一次可以跳上1级台阶，也可以跳上2级……也可以跳上n级。求跳上一个n级的台阶总共有多少种跳法。
因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+…+f(1)
因为f(n-1)=f(n-2)+f(n-3)+…+f(1)
所以f(n)=2*f(n-1)

function jumpII(number)
{
    if(number == 0){
        return 0;
    }else if(number == 1){
        return 1;
    }
    return 2*jumpII(number-1)
}

斐波那契数列

斐波那契数列，又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……

性能优化之缓存

• 缓存: 存储数据的容器(cache)
• 在js中, 可以使用数组或者是对象进行存储数据,用键存储值,这样就可以实现既能存值也能取值

用缓存的基本思路

1. 创建一个空对象，作为缓存的容器。
2. 首先去缓存容器中查看缓存中是否有对应的数据，如果有，直接取出来使用。
3. 如果没有，就先计算结果，然后把结果存储到缓存容器中，方便下次复用。

   var cache = { };
   var count = 0;
   function fib(n){
       count++;
       if(n === 1 || n === 2){
           return 1;
       }
       if(cache[n]){
           return cache[n];
       }else{
           var ret = fib(n - 1) + fib(n - 2);
           cache[n] = ret;
           return ret;
       }
   }
   
   console.log(fib(10));
   console.log("fib函数调用的次数 " + count);

总结

• 缓存: 存数据(该案例中,用键存月份,值存的对数)
• 在js中,缓存中如何表示, 对象 || 数组