A-A+

爬楼梯- 解法

2020年09月21日 算法 暂无评论 阅读 1 次

第一种思路代码

var climbStairs = function(n) {
  const dp = new Array(n+1).fill(0)
   dp[0] = 1;
   dp[1] = 1;

  for(let i =2;i<dp.length;i++ ){
    dp[i] = dp[i-2]+dp[i-1]
  }
  return dp[n]
};

第二种思路
标签:动态规划
本问题其实常规解法可以分成多个子问题,爬第n阶楼梯的方法数量,等于 2 部分之和

爬上 n-1n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
爬上 n-2n−2 阶楼梯的方法数量,因为再爬2阶就能到第n阶
所以我们得到公式 dp[n] = dp[n-1] + dp[n-2]dp[n]=dp[n−1]+dp[n−2]
同时需要初始化 dp[0]=1dp[0]=1 和 dp[1]=1dp[1]=1
时间复杂度:O(n)O(n)

错误

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {

  function deal(num) {
    if (num === 2) {
     return  2;
    }else if(num ===1){
      return  1;
    } else {
      return  deal(num-1) + deal(num-2) ;
    }
  }

  return   deal(n);

};

标签:

给我留言

Copyright © web前端技术开发个人博客 保留所有权利  京ICP备14060653号 Theme  Ality

用户登录