Climbing Stairs（爬楼梯）

题目 / Problem

中文： 你正在爬楼梯，需要走 n 级台阶才能到达楼顶。

每次可以爬 1 级或 2 级台阶。请问共有多少种不同的方法可以到达楼顶？

English: You are climbing a staircase. It takes n steps to reach the top.

Each time, you can climb either 1 or 2 steps. In how many distinct ways can you climb to the top?

示例 / Examples

Example 1

Input:  n = 2
Output: 2

解释 / Explanation:
共有两种方法到达楼顶：
There are two ways to reach the top:

1. 1 级 + 1 级 / 1 step + 1 step
2. 2 级 / 2 steps

Example 2

Input:  n = 3
Output: 3

解释 / Explanation:
共有三种方法到达楼顶：
There are three ways to reach the top:

1. 1 级 + 1 级 + 1 级 / 1 step + 1 step + 1 step
2. 1 级 + 2 级 / 1 step + 2 steps
3. 2 级 + 1 级 / 2 steps + 1 step

解题思路：动态规划 / Approach: Dynamic Programming

考虑到达第 i 级台阶时的最后一步：
Consider the final move used to reach step i:

如果最后爬 1 级，那么之前必须位于第 i - 1 级。
If the final move climbs 1 step, the previous position must be step i - 1.
如果最后爬 2 级，那么之前必须位于第 i - 2 级。
If the final move climbs 2 steps, the previous position must be step i - 2.

这两种情况互不重叠，因此到达第 i 级的方法数为：
These two cases do not overlap, so the number of ways to reach step i is:

ways(i) = ways(i - 1) + ways(i - 2)

初始状态：
Base cases:

ways(1) = 1
ways(2) = 2

这个递推关系与 Fibonacci 数列相同，只是初始位置有所偏移。
This recurrence matches the Fibonacci sequence with shifted initial values.

空间优化 / Space Optimization

计算 ways(i) 时只需要前两个状态，不必保存整个动态规划数组。使用两个变量：
Calculating ways(i) requires only the previous two states, so the entire dynamic-programming array is unnecessary. Use two variables:

previousTwo：到达第 i - 2 级的方法数。
previousTwo: ways to reach step i - 2.
previousOne：到达第 i - 1 级的方法数。
previousOne: ways to reach step i - 1.

每轮计算当前状态后，将两个变量向前滚动。
After calculating the current state, roll both variables forward.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number} n
 * @return {number}
 */
function climbStairs(n) {
  if (n <= 2) {
    return n;
  }

  let previousTwo = 1;
  let previousOne = 2;

  for (let step = 3; step <= n; step++) {
    const current = previousOne + previousTwo;
    previousTwo = previousOne;
    previousOne = current;
  }

  return previousOne;
}

执行过程 / Walkthrough

以 n = 5 为例：
For n = 5:

台阶 / Step	计算 / Calculation	方法数 / Ways
1	初始状态 / Base case	1
2	初始状态 / Base case	2
3	`ways(2) + ways(1) = 2 + 1`	3
4	`ways(3) + ways(2) = 3 + 2`	5
5	`ways(4) + ways(3) = 5 + 3`	8

因此到达第 5 级台阶共有 8 种方法。
Therefore, there are 8 distinct ways to reach step 5.

复杂度 / Complexity

时间复杂度：O(n)，从第 3 级遍历到第 n 级。
Time: O(n), because the algorithm iterates from step 3 through step n.
空间复杂度：O(1)，只保存前两个状态和当前状态。
Space: O(1), because only the previous two states and the current state are stored.

动态规划数组解法 / DP Array Approach

如果希望直接查看每一级台阶的方法数，也可以使用数组保存所有状态：
To inspect the number of ways for every step directly, store all states in an array:

function climbStairsWithArray(n) {
  if (n <= 2) {
    return n;
  }

  const ways = new Array(n + 1);
  ways[1] = 1;
  ways[2] = 2;

  for (let step = 3; step <= n; step++) {
    ways[step] = ways[step - 1] + ways[step - 2];
  }

  return ways[n];
}

时间复杂度 / Time: O(n)
空间复杂度 / Space: O(n)

数组解法更直观，但空间优化版本只需要 O(1) 额外空间。
The array solution is more explicit, but the optimized version needs only O(1) extra space.

朴素递归的问题 / Problem with Naive Recursion

直接按照递推式递归会重复计算大量相同状态：
Recursing directly from the recurrence repeatedly calculates the same states:

function climbStairsSlow(n) {
  if (n <= 2) {
    return n;
  }

  return climbStairsSlow(n - 1) + climbStairsSlow(n - 2);
}

它的时间复杂度约为 O(2ⁿ)，当 n = 45 时会非常慢。动态规划通过保存或滚动复用已经计算的状态，将时间复杂度降低为 O(n)。
Its time complexity is approximately O(2ⁿ), which is very slow when n = 45. Dynamic programming reuses previously calculated states and reduces the time complexity to O(n).

易错点 / Common Pitfalls

初始状态是 ways(1) = 1、ways(2) = 2，不是标准 Fibonacci 数列中的 0 和 1。
The base cases are ways(1) = 1 and ways(2) = 2, not the standard Fibonacci values 0 and 1.
每种方法的顺序不同也算不同方案，例如 1 + 2 与 2 + 1。
Different step orders count as distinct ways, such as 1 + 2 and 2 + 1.
循环应从第 3 级开始，并包含第 n 级。
Start the loop at step 3 and include step n.
更新滚动变量时，应先保存当前结果，避免覆盖仍需使用的旧状态。
Save the current result before rolling the variables forward so a required old state is not overwritten.
朴素递归会产生大量重复计算，不适合本题上限。
Naive recursion performs extensive repeated work and is unsuitable for the upper constraint.

Climbing Stairs