#77

Climbing Stairs

easy

Open in editor

mathdynamic-programmingmemoization

You are climbing a staircase with n steps. Each move you may climb either 1 or 2 steps.

Return the number of distinct ordered ways you can reach the top.

Example

Input: n = 2

Output: 2

Either 1+1 or a single 2-step.

Constraints

1 <= n <= 45

Intuition

A first pass just recurses straight on the definition: the number of ways to reach step n is the number of ways to reach n-1 plus the number of ways to reach n-2, recomputed from scratch every time either is needed.

function climbStairs(n) {
  // Reaching stair 0 (stand still) or stair 1 (a single 1-step) each has exactly one way.
  if (n <= 1) return 1;
  // The last move into stair n was either a 1-step from n-1 or a 2-step from n-2;
  // recurse into both and sum, with no memory of anything already solved.
  return climbStairs(n - 1) + climbStairs(n - 2);
}

Brute force — naive recursion on the recurrence, no caching: O(2ⁿ).

This is O(2ⁿ) — exponential, because the same subproblem gets solved over and over. climbStairs(5) calls climbStairs(4) and climbStairs(3), but climbStairs(4) also calls climbStairs(3) — and both of those recurse all the way back down through climbStairs(1) and climbStairs(0) many times over. Can we do better?

The key observation: climbStairs(i) only ever depends on climbStairs(i-1) and climbStairs(i-2), and once a state is solved its answer never changes — so it only needs to be computed once. That's the overlapping-subproblems signature dynamic programming exists for: memoize each state's answer top-down, or fill a table of them bottom-up.

The stored solution takes the bottom-up route, and immediately space-optimizes it: since dp[i] only ever reads the two values directly behind it, there's no need to keep a whole array — two rolling variables are enough. In the code, prev and curr are exactly dp[i-2] and dp[i-1] from the walkthrough below, slid one step forward each iteration instead of written into a full table.

Walking it through:

dp[i] = ways to reach stair i, for i = 0..5 (n = 5)

i↓

dp[0] = 1

Base case: there's exactly one way to be standing at the ground — take zero steps.

i↓

dp[1] = 1

Base case: exactly one way to reach stair 1 — a single 1-step. `marked` means "already filled", not "discarded" — dp[0] stays available to read.

i↓

dp[2] = dp[1] + dp[0] = 1 + 1 = 2

First real transition: reach stair 2 either via a last 1-step from stair 1, or a last 2-step from stair 0. Both are already sitting in the table.

i↓

dp[3] = dp[2] + dp[1] = 2 + 1 = 3

Without a table, computing this fresh would recurse back through dp[1] and dp[0] all over again — the table reads each of them exactly once.

i↓

dp[4] = dp[3] + dp[2] = 3 + 2 = 5

Same recurrence, one step further — dp[3] and dp[2] are both already computed.

i↓

dp[5] = dp[4] + dp[3] = 5 + 3 = 8

Final state: 8 distinct ways to climb 5 stairs.

Optimization

Bottom-up Fibonacci

The ways to reach step i equal the ways to reach i-1 (then a single step) plus the ways to reach i-2 (then a double step), which is the Fibonacci recurrence. Track only the last two values.

O(n) time, O(1) space.

function climbStairs(n) {
  // Base cases folded in: dp[0] = dp[1] = 1, tracked as the last two values.
  let prev = 1; // dp[i - 2]
  let curr = 1; // dp[i - 1]
  for (let i = 2; i <= n; i++) {
    const next = prev + curr; // dp[i] = dp[i - 2] + dp[i - 1]
    prev = curr; // slide the window forward: dp[i - 2] <- dp[i - 1]
    curr = next; // dp[i - 1] <- dp[i]
  }
  return curr; // dp[n]; for n <= 1 the loop never runs and curr is already 1
}

Complexity analysis

Time complexity: O(n). Here's why:

The loop runs once for each step from 2 up to n — n - 1 iterations.
Each iteration does O(1) work: one addition and two assignments to slide prev/curr forward.

So the whole fill is O(n), down from the brute force's O(2ⁿ) — every state is computed exactly once instead of being re-derived on every path that needs it.

Space complexity: O(1). Here's why:

Only two rolling variables, prev and curr, are kept — never a full dp array of size n.
There's no recursion, so no call stack either.

That's the space-optimization on top of the DP itself: a bottom-up table would already be O(n) time, but a naive table fill costs O(n) space too; collapsing it to the last two values, since dp[i] never reads anything further back, gets time and space to O(n) and O(1).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
n = 1	1	Smallest input allowed by the constraints — the base case, no transitions run.
n = 9	55	Small but past the base cases — exercises several chained transitions.
n = 12	233	Mid-size input; the answer has grown past three digits.
n = 25	121393	Large enough that the brute force's 2ⁿ recursive calls would be impractical, while the O(n) fill barely notices.
n = 43	701408733	Near the top of the allowed range (n <= 45); the running total stays a safe integer.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor