经典跳台阶

题目

一只青蛙一次可以跳上一级台阶，也可以跳上2级

求该青蛙跳上一个n级的台阶总共有多少中跳法

思考

当青蛙要跳上第n级的时候，它可以在第n-1级跳一级，也可以在第n-2级跳两级

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

代码

普通递归

这个也是最容易想到的解决方案，但是容易造成数据的重复计算，容易爆栈

function jumpfloor(n){
    if(n<3){
        return n;
    }
    return jumpfloor(n-1)+jumpfloor(n-2);
}

记忆化递归（存储算过的值）

在计算两个值相加的时候，另一边又要重复一遍相同的计算，提前存好计算过的值可以大大提高运算效率

let cache = [0,1,2];
function jumpfloor(n){
    if(cache[n]===undefined){
        cache[n]= jumpfloor(n-1)+jumpfloor(n-2);
    }
    return cache[n];
}

或者也可以自底向上存储每个值

let arr = [0,1,2];
function jumpfloor(n){
    for(let i = 3;i<=n;i++){
        arr[i] = arr[i-1] + arr[i-2];
    }
    return arr[n];
}

存储两个值

在递归过程中存储两个值即可直接计算出下一个值

function jumpfloor(n) {
    let a = 1;
    let b = 2;
    for (let i = 3; i <= n; i++) {
        b = a + b;
        a = b - a;
    }
    return b;
}