LeetCode 70 · Fibonacci

Climbing Stairs

EasyCount the ways to climb n stairs taking 1 or 2 steps at a time.
You are climbing a staircase that 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?

Intuition

To reach step i your last move was either a 1-step (from i−1) or a 2-step (from i−2).

So ways(i) = ways(i−1) + ways(i−2) — the Fibonacci recurrence.

Only the previous two values are ever needed, so we can keep two rolling variables instead of a full array.

The algorithm

  1. 01Base cases: there is 1 way to stand at the bottom and 1 way to reach the first step.
  2. 02Keep a = ways(i−2) and b = ways(i−1).
  3. 03Each iteration advance the window: (a, b) → (b, a + b).
  4. 04After n iterations a holds ways(n).

Reference implementation

1
function climbStairs(n) {
2
  let a = 1, b = 1; // ways to reach steps i-2 and i-1
3
  for (let i = 0; i < n; i++) {
4
    [a, b] = [b, a + b];
5
  }
6
  return a;
7
}

Complexity

Time
O(n) — a single loop.
Space
O(1) — two rolling variables.