原题

一、题目内容 简单

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

输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例2：

输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

  二、解题思路

1. 确定 dp 数组的含义

dp[i]：爬到第 i 阶，有 dp[i] 种方法

1. 递推公式

到第 1 阶，只能走 1 步，故是 dp[1] = 1
到第 2 阶，dp[2] 等于第 1 阶走一步，或者第 0 阶走两步，dp[2] = dp[1] + dp[0]
到第 3 阶，dp[3] 等于第 2 阶走一步，或者第 1 阶走两步，dp[3] = dp[2] + dp[1]
到第 n 阶，dp[n] 等于第 n - 1 阶走一步，或者第 n - 2 阶走两步，dp[n] = dp[n-1] + dp[n-2]

1. dp 数组初始化

dp[0] = dp[1] = 1

三、具体代码

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  // dp[i]：爬到第 i 阶，有 dp[i] 种方法
  const dp = [1, 1]
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
};

四、其他解法

题目变体

一、题目内容 中等

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

示例1：

输入: m = 3，n = 3 输出: 4 解释：有三种方法可以爬到楼顶。

1. 1 阶+ 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
4. 3 阶

示例2：

输入: m = 7, n = 4 解释：有八种方法可以爬到楼顶。

1. 1 阶+ 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶 + 1 阶
3. 2 阶 + 1 阶 + 1 阶
4. 1 阶 + 1 阶 + 2 阶
5. 2 阶 + 2 阶
6. 1 阶 + 3 阶
7. 3 阶 + 1 阶
8. 4 阶

二、解题思路

1. 确定dp数组以及下标的含义

**dp[i]**：爬到有 i 个台阶的楼顶，有**dp[i]**种方法。

1. 确定递推公式

本题呢，dp[i]有几种来源，dp[i - 1]，dp[i - 2]，dp[i - 3] 等等，即：dp[i - j]
那么递推公式为：dp[i] += dp[i - j]

1. dp 数组如何初始化

既然递归公式是 dp[i] += dp[i - j]，那么dp[0]一定为 1，dp[0]是递归中一切数值的基础所在，如果dp[0]是 0 的话，其他数值都是 0 了。
下标非 0 的 dp[i] 初始化为0，因为 dp[i] 是靠 dp[i-j] 累计上来的，dp[i]本身为 0 这样才不会影响结果

1. 确定遍历顺序

这是背包里求排列问题，即：1、2 步 和 2、1 步都是上三个台阶，但是这两种方法不一样！
所以需将 target 放在外循环，将 nums 放在内循环。
每一步可以走多次，这是完全背包，内循环需要从前向后遍历。

三、具体代码

const climbStairs = function (n, m) {
  // dp[i]：爬到第 i 阶有 dp[i] 种方法
  const dp = new Array(n + 1).fill(0)
  // 初始化 dp 数组
  dp[0] = 1
  // 遍历背包
  for (let i = 1; i <= n; i++) {
    // 遍历物品
    for (let j = 1; j <= m; j++) {
      if (i >= j) dp[i] += dp[i - j]
    }
  }
  return dp[n]
}

四、其他解法