简单

问题描述

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

动态规划

使用 $dp(i)$ 表示爬到第 $i$ 级台阶的方案数

• 当 $i = 1$ 时，只能直接爬到第一级阶梯。
• 当 $i = 2$ 时，可以一开始直接一次爬两阶到第二级阶梯，也可以先爬到第一级阶梯再爬到第二级阶梯。
• 当 $i > 2$ 时，可以选择从第 $i - 2$ 级阶梯一次爬两阶到第 $i$ 级阶梯，也可以从第 $i - 1$ 级阶梯爬一级到第 $i$ 级阶梯。

状态转移方程如下：

$$dp(i)= \begin{cases} 1 & i = 0 \\ 2 & i = 2 \\ dp(i - 1) + dp(i - 2) & i > 2 \\ \end{cases}$$

由于 $dp(x)$ 只和 $dp(x - 1)$ 与 $dp(x - 2)$ 相关，可以使用滚动数组优化空间复杂度。

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n === 1) return 1
  if (n === 2) return 2
  const dp = [1, 2]
  for (let i = 2; i < n; i++) {
    dp[1] = dp[0] + dp[1]
    dp[0] = dp[1] - dp[0]
  }
  return dp[1]
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$