前端刷题路-Day21｜刷题打卡

掘金团队号上线，助你 Offer 临门！ 点击 查看详情

爬楼梯（题号70）

题目

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

链接

leetcode-cn.com/problems/cl…

解释

乍一看一脸懵逼，仔细一看就是斐波那契数列，问题迎刃而解。

自己的答案（简单递归）

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

确实很简单，但递归次数太多，会直接超时，无法采用

自己的答案（递归+记忆化）

var climbStairs = function(n) {
  var res = [0,  1, 2]
  function findNum(n) {
    if (!res[n]) {
      res[n] = (res[n - 1] || findNum(n - 1)) + (res[n - 2] || findNum(n - 2))
      return res[n]
    }
    return res[n]
  }
  return findNum(n)
};

利用res存储已经算过的值，如果有直接取，如果没有则开始i计算。

其实这种方法的性能已经不错了，跑了几次，最高能到90%以上，也不知道为啥，但仍然有更优解。

自己的答案（动态规划）

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

先给res赋值，为了解决n是1或者2的情况。

之后从3开始循环，直到i等于n，每次新的i值等于前两位的和。

最后取res的最后一位即可。

倒序思想，从小到大递增，简单易懂。

自己的答案（动态规划升级）

从?的答案可以看出来，其实每次n只要取n-1和n-2的值即可，那么数组里是不是只要留两个值就行了？答案是可以的：

var climbStairs = function(n) {
  if (n <= 2) return n
  var res = [1, 2]
  for (let i = 3; i < n + 1; i++) {
    res = [res[1], res[0] + res[1]]
  }
  return res[1]
};

当然了，其实用两个变量来代替res[0]和res[1]也可以，性能上的细微差别。

更好的方法

更好的方法当然是有的，但笔者这辈子是不可能想出来的，有两种：

1. 矩阵快速幂

2. 通项公式

有兴趣的同学可以看看LeetCode的官方题解，说的比较详细：leetcode-cn.com/problems/cl…

PS：想查看往期文章和题目可以点击下面的链接：

这里是按照日期分类的?

前端刷题路-目录（日期分类）

经过有些朋友的提醒，感觉也应该按照题型分类
这里是按照题型分类的?

前端刷题路-目录（题型分类）

有兴趣的也可以看看我的个人主页?

Here is RZ