70. 爬楼梯｜刷题打卡

闲时要有吃紧的心思，忙时要有悠闲的趣味

• 题目描述
• 思路分析
• AC 代码
• 总结

题目描述

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

思路分析

 是不是觉得这道题似曾相识？

 例如第 N 阶的楼梯，有几种方式能够跳上来呢？只有(n - 1)和(n - 2)阶楼梯能跳上来。

 依次类推，每一阶楼梯只有其(n - 1)和(n - 2)能跳上来，除了 1 阶和 2 阶楼梯。

 没错，这就是斐波那契数列。

 我是没办法吧斐波那契讲出花来了，有需要可以看这个超棒题解

思路一：递归

 说到斐波那契，最经典解法的要数递归了。但是会超时……

思路二：滚动数组

就是这样的：

AC 代码

递归

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n === 1) return 1
  if (n === 2) return 2
  return climbStairs(n - 1) + climbStairs(n - 2)
}

题解二：滚动数组

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  let p = 0,
    q = 0,
    r = 1
  for (let i = 1; i <= n; ++i) {
    p = q
    q = r
    r = p + q
  }
  return r
}

总结

 三月你好，春暖花开。加油！

 本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情

后记：Hello 小伙伴们，如果觉得本文还不错，记得点个赞或者给个 star，你们的赞和 star 是我编写更多更丰富文章的动力！GitHub 地址

文档协议