一道关于爬楼梯的算法题目

Question

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

我按照波非那切的思路写了如下代码，但感觉有问题，速度好慢，大家有没有其他实现方法；

var climbStairs = function(n) {
    if(n==1){
        return 1
    }else if(n==2){
        return 2
    }else {
        return climbStairs(n-1)+climbStairs(n-2)
    }
};

我是这样解释代码的，一个台阶 就是一次，
有两个台阶就是2次，
所以又f(1)=1,f(2)=2;
n个台阶时，假设第一步走一个台阶，那么剩下n-1个台阶，n-1个台阶就有f（n-1）种情况;
如果第一步走两个台阶，剩下n-2个台阶,就有f(n-2)种情况,二者合并就是n个台阶的总走法；
所以产出如上代码；

Answer 1

爬楼梯问题其实是动态规划的一类问题
题主你只要通过这个问题稍稍的思考一下，使用递归解法为什么会慢？
因为递归造成了大量的重复子问题，假设走十阶台阶
递归立马要去算怎么走到第九阶，怎么走到第八阶 因为f(10) = f(9) + f(8)

然后一层一层下去，中间造成了大量的浪费，其实我们只要将每一阶的走法存下来就可以避免重复计算了

举例来说：

我们从后往前看，当我已经到达三阶楼梯的时候，是怎样上来的呢？
f(3) = f(2) + f(1) // 从第二阶走一步上来或者从第一阶走两步上来
归纳一下
f(n) = f(n-2) + f(n-1) // 从第n-2阶台阶走一步上来或者从第n-1阶台阶走两步上来

我们只要通过递推的方式就能快速的得到答案

function Fibonacci(n) {
    var a = [0, 1, 2]
    for (var i = 3; i <= n; i++) {
        a[i] = a[i-1] + a[i-2]
    }
    return a[n]
}

Answer 2

使用尾递归优化下

function fibonacci (n , a = 1 , b = 2) {
  if( n <= 1 ) {return a};
  return fibonacci (n - 1, b, a + b);
}

Answer 3

把中间结果缓存起来可以加速

Answer 4

 function instart(n){
    if(n >= 100) return 0;
    return 1 + instart(n + (Math.floor(Math.random()*2+1)))
  }
  instart(0)