计算有多少种方法爬楼梯

题目-爬楼梯 #

假设你正在爬楼梯，需要 n 步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

示例 #

比如 n=3，1+1+1=1+2=2+1=3，共有 3 种不同的方法   返回 3

分析 #

规则可以采用不完全归纳法看看：

0 =0 0种方法
1 = 1 种方法
2 = 1+1 =2 2种方法
3 = 1+1+1=1+2=2+1 3种方法
4 = 1*4 = 1+2+1 = 1+1+2 = 2+1+1 = 2+2 5种方法
5 = 1*5 = 2+1+2 =2+2+1 = 1+2+2 =1+2+1+1 = 1+1+2+1 = 2+1+1+1 = 1+1+1+2 8种方法

简单的想法就是递归, 爬到第n层的组合数等于第n-1层和第n-2层的组合数之和

Just Try #

请你自动动手试一下：在线编程环境

想想有没有其他思路？

想想时间和空间复杂度，能否优化一下

真的做不到么？

let you think， think makes you happy!

参考答案 #

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

代码复制到在线编程环境试一下：在线编程环境

性能问题 #

上面代码有性能问题，你把输入改成 100 试试。 ~会卡死一会，经我测试，入参45，可以勉强算出来。~_~

另外一种方法就是正向计算，参考：查找斐波纳契数列中第 N 个数

交换变量 #

看网上有一种交换变量的写法，其实和正向计算是一样的，只不过空间复杂度降到个位，之前用数据来正向计算空间复杂度是n

function algorithm(n){
    if(n==0) return 0;
    if(n==1) return 1;
    if(n==2) return 2;
    let [a,b]=[1,2];
    for(let i=3; i<= n; i++){
      [a,b] = [b, a + b]
    }
    return b
  }