Climbing Stairs

The problem. You're climbing a staircase with n steps. Each move climbs 1 or 2 steps. In how many distinct ways can you reach the top?

Example

n = 2  ->  2   (1+1, 2)
n = 3  ->  3   (1+1+1, 1+2, 2+1)
n = 5  ->  8

The pattern: 1D DP

In 1D DP the state is a single index — usually "the answer for the first i items" or "for step i". The recurrence looks back a fixed number of positions (one or two), so the table fills left to right and almost always shrinks to a couple of variables. This chapter goes from counting (Climbing Stairs) to minimising (Min Cost), to take-or-skip choices (House Robber), a circular twist (House Robber II), and a string version (Decode Ways).

The idea

Think about the last move. To stand on step i, you came either from step i − 1 (a 1-step) or from step i − 2 (a 2-step). Those two groups of ways don't overlap and cover everything, so ways[i] = ways[i − 1] + ways[i − 2]. There's one way to be on step 0 (do nothing) and one way to reach step 1.

1. Plain recursion

1function climbStairs(n) {2  if (n <= 1) return 1;                         // step 0 or 1: one way3  return climbStairs(n - 1) + climbStairs(n - 2);   // last move was 1 step or 2 steps4}

Time O(2ⁿ), space O(n). The same call tree as Fibonacci — n = 45 would take minutes.

2. A table, filled left to right

1function climbStairs(n) {2  const ways = new Array(n + 1).fill(0);     // ways[i]: ways to stand on step i3  ways[0] = 1;4  ways[1] = 1;5  for (let i = 2; i <= n; i++) {6    ways[i] = ways[i - 1] + ways[i - 2];     // from one step below, or two7  }8  return ways[n];9}

Time O(n), space O(n).

3. Two variables

1function climbStairs(n) {2  let twoBelow = 1, oneBelow = 1;            // ways[i - 2], ways[i - 1]3  for (let i = 2; i <= n; i++) [twoBelow, oneBelow] = [oneBelow, twoBelow + oneBelow];4  return oneBelow;5}

Time O(n), space O(1). Only the last two counts are ever read.

Comparing the approaches

Edge cases to test

Variations