计算有多少种方法爬楼梯

题目-爬楼梯

假设你正在爬楼梯,需要 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
  }

 

知识共享署名4.0国际许可协议,转载请保留出处; 部分内容来自网络,若有侵权请联系我:前端学堂 » 计算有多少种方法爬楼梯

赞 (2) 打赏

评论 0

如果对您有帮助,别忘了打赏一下宝宝哦!

支付宝扫一扫打赏

微信扫一扫打赏