Climbing Stairs

Examples

Input: n = 2
Output: 2

1 step + 1 step, or 2 steps.

Input: n = 3
Output: 3

1+1+1, 1+2, or 2+1.

Constraints

• 1 <= n <= 45

Approach

Think about the very last move you'd take to land exactly on step n: it was either a 1-step move from step n-1, or a 2-step move from step n-2. So the number of ways to reach step n is simply the number of ways to reach step n-1 plus the number of ways to reach step n-2 — the same pattern as the Fibonacci sequence.

Naively recomputing this recursively re-does the same smaller subproblems over and over. Building the answer up from the smallest steps, and reusing each result once it's computed, avoids all that repeated work.

Solutions

Brute Force — Plain Recursion

Directly recurse: the ways to reach n is ways(n-1) + ways(n-2). Correct, but recomputes the same subproblems exponentially many times.

function climbStairs(n) {
  if (n <= 2) return n;
  return climbStairs(n - 1) + climbStairs(n - 2);
}

Time: O(2^n) · Space: O(n) — recursion depth

Optimal — Bottom-Up with Two Variables

Since each step only ever needs the previous two results, there's no need to store the whole history — just keep the last two values and slide them forward.

function climbStairs(n) {
  if (n <= 2) return n;

  let prev2 = 1;
  let prev1 = 2;

  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

Time: O(n) · Space: O(1)