Climbing Stairs

EasyDynamic ProgrammingMathDynamic ProgrammingMemoization

Problem

You start at the bottom of a staircase with a fixed number of steps, and each move you take advances you either one step or two. Count how many distinct sequences of moves land you exactly on the top step.

Example. For a 4-step staircase, there are 5 distinct sequences: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, and 2+2.

Key idea

Enumerating every sequence of moves directly branches into two choices at each step, so the count of paths explodes exponentially, and a plain recursive solution keeps re-solving the same smaller staircases.

The way out: however you reach step n, your last move was either a single step from n - 1 or a double step from n - 2, and those two cases cover every possibility with no overlap. So the ways to reach step n is the sum of the ways to reach n - 1 and n - 2: the Fibonacci recurrence in disguise. Building the counts upward from the base cases (one way to stand at the ground, one way to reach the first step) means each new value only needs the two before it, so nothing is ever recomputed.

Solution

function climbStairs(n: number): number {
  let oneStepBack = 1; // ways to reach the previous step
  let twoStepsBack = 1; // ways to reach the step before that

  for (let step = 2; step <= n; step++) {
    const current = oneStepBack + twoStepsBack; // last move was 1 step or 2 steps back
    twoStepsBack = oneStepBack;
    oneStepBack = current;
  }

  return oneStepBack;
}

Complexity

  • Time: O(n). One pass computing the count for each step from the bottom up.
  • Space: O(1). Only the previous two counts need to be kept at any time.

Watch out for

  • Get the base cases right: one way to stand at the ground (zero moves), one way to have reached the first step.
  • Plain top-down recursion without memoization is exponential; either cache results or switch to the bottom-up iterative version.
  • This counts ordered sequences of moves, so a 1-then-2 sequence and a 2-then-1 sequence count separately.

Pattern

This is the simplest instance of "current state depends on a fixed window of prior states," the same shape that drives House Robber and Decode Ways, where a running answer is built from one or two previously solved smaller answers instead of branching into a full recursion tree.

Related questions