1. 题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。
示例 1：**

  1. 输入： 2
  2. 输出： 2
  3. 解释： 有两种方法可以爬到楼顶。
  4. 1.  1 阶 + 1 阶
  5. 2.  2 阶

示例 2：

  1. 输入： 3
  2. 输出： 3
  3. 解释： 有三种方法可以爬到楼顶。
  4. 1.  1 阶 + 1 阶 + 1 阶
  5. 2.  1 阶 + 2 阶
  6. 3.  2 阶 + 1 阶

2. 解题思路

看到这个题目，我们应该想到的就是动态规划，将一个大问题分解成多个子问题。首先来看：

  • 第一级台阶：1种方法
  • 第二级台阶：2种方法
  • 第n级台阶：从第n-1级台阶爬一级，或从第n-2级台阶爬2级

所以可以得出递推公式：f(n) = f(n−1) + f(n−2)
这样，我们就可以通过递归完成计算。

复杂度分析：**

  • 时间复杂度：O(n)，递归树的深度为n，所以时间复杂度为O(n)；
  • 空间复杂度：O(n)，这里需要初始化一个数组用来保存每一层台阶的方法数，有n个数，所以空间复杂度为O(n)；

上面这种普通递归很显然，有很多的重复计算，所以，我们可以将每次计算的结果进行保存，以便下次计算时直接使用。

复杂度分析：

  • 时间复杂度：O(n)，需要循环执行n次，所以时间复杂度为O(n)；
  • 空间复杂度：O(1)，这里只用了常数个变量作为辅助空间，所以空间复杂度为 O(1)；

    3. 代码实现

    普通递归：
    1. /**
    2. * @param {number} n
    3. * @return {number}
    4. */
    5. var climbStairs = function(n) {
    6.   const dp = []
    7.   dp[0] = 1
    8.   dp[1] = 1
    9.   for(let i = 2; i <= n; i ++){
    10.       dp[i] = dp[i - 1] + dp[i - 2]
    11.   }
    12.   return dp[n]
    13. };
    记忆递归：
    1. /**
    2. * @param {number} n
    3. * @return {number}
    4. */
    5. var climbStairs = function(n) {
    6.   let a = 1, b = 1, res = 1;
    7.   for (let i = 1; i < n; i++) {
    8.       a = b
    9.       b = res
    10.       res = a + b
    11.   }
    12.   return res
    13. };

    4. 提交结果

    普通递归：

    image.png

    记忆递归：

    image.png