Frontend Beauty
ESC

Type to search the knowledge base.

Climbing Stairs

n steps, take 1 or 2 at a time — Fibonacci DP, bottom-up O(1) space, and the recursion trap interviewers watch for.

beginner3 min read
  • dsa
  • dp
  • interview
  • Google
  • Meta

The problem

You are climbing a staircase with n steps. Each move takes 1 or 2 steps. How many distinct ways to reach the top?

n = 2 → 2   // 1+1, 2
n = 3 → 3   // 1+1+1, 1+2, 2+1

Order matters. This is Fibonacci with a shifted index.

Brute force: plain recursion

function climbStairsBrute(n: number): number {
  if (n <= 2) return n;
  return climbStairsBrute(n - 1) + climbStairsBrute(n - 2);
}
Time O(2^n)
Space O(n) stack

Dies for n ≥ ~40. Mention memoization next.

Memoized recursion

function climbStairsMemo(n: number): number {
  const memo = new Map<number, number>();
  function f(k: number): number {
    if (k <= 2) return k;
    if (memo.has(k)) return memo.get(k)!;
    const ans = f(k - 1) + f(k - 2);
    memo.set(k, ans);
    return ans;
  }
  return f(n);
}
Time O(n)
Space O(n)

Optimal: bottom-up O(1) space

ways(i) = ways(i-1) + ways(i-2)
ways(1)=1, ways(2)=2

Only need the last two values.

function climbStairs(n: number): number {
  if (n <= 2) return n;
  let a = 1; // ways(1)
  let b = 2; // ways(2)
  for (let i = 3; i <= n; i++) {
    const c = a + b;
    a = b;
    b = c;
  }
  return b;
}
Time O(n)
Space O(1)

Table

n ways
1 1
2 2
3 3
4 5
5 8

Edge cases

  • n = 1
  • Large n (LC up to 45) — int fine in JS Number for this range
  • Follow-up: k step sizes → full DP array

Common mistakes

  • Off-by-one base cases (ways(0)=1 is valid empty path framing — stay consistent)
  • Shipping exponential recursion without mentioning complexity
  • Confusing combinations with permutations (order matters here)

Interview delivery

  1. Recurrence from last step 1 or 2.
  2. Show exponential recursion, then DP.
  3. Roll array to O(1) space.
  4. Fibonacci connection.

Mental model

Each path is a sequence of 1s and 2s that sum to n. The count of sequences is exactly the Fibonacci recurrence because the last step is forced into two cases. Drawing the tree for small n makes the overlapping subproblems obvious — f(5) recomputes f(3) many times without memo.

If the problem allowed steps of size {1,2,...,k}, the recurrence becomes f(n) = sum f(n-i) for i=1..k with a sliding window sum optimization. Interviewers sometimes pivot there after you ship the classic version.

Complexity table (all approaches)

Approach Time Space Ship in interview?
Plain recursion O(2^n) O(n) only to dismiss
Memo DFS O(n) O(n) yes
DP array O(n) O(n) yes
Two variables O(n) O(1) preferred
Matrix expo / closed form O(log n) O(1) flex if asked

Out-loud answer (30s)

“Ways to climb n with 1 or 2 steps is Fibonacci. Base 1 and 2, then each step sum of previous two. I’ll roll two integers for O(n) time O(1) space. For n=1 return 1. If you allowed k step sizes I’d keep a DP array or window sum.”

Further reading