Skip to main content

70. Climbing Stairs

easyAsked at DRW

DRW uses Climbing Stairs to probe whether candidates recognize Fibonacci-structure recurrences and immediately space-optimize. The follow-up — counting paths under a step-size constraint — mirrors the combinatorics in option-path counting and lattice models.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DRW loops.

  • Glassdoor (2025-Q4)— DRW phone screen candidates report dynamic-programming warm-ups including Climbing Stairs as a prelude to harder DP problems.
  • Blind (2025-10)— DRW interview threads note Climbing Stairs is used to test DP space-optimization instinct before moving to lattice-path problems in follow-ups.

Problem

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Constraints

  • 1 <= n <= 45

Examples

Example 1

Input
n = 2
Output
2

Explanation: 1+1 or 2. Two ways.

Example 2

Input
n = 3
Output
3

Explanation: 1+1+1, 1+2, or 2+1. Three ways.

Approaches

1. Space-optimized DP (Fibonacci)

ways(n) = ways(n-1) + ways(n-2) with base cases ways(1)=1, ways(2)=2. Keep only the last two values — no array needed.

Time
O(n)
Space
O(1)
function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff: O(n) time, O(1) space. Always lead with this at DRW — the O(n) array version is correct but wastes memory for no benefit.

2. Memoized recursion (top-down DP)

Recursively compute ways(n) = ways(n-1) + ways(n-2), caching results in a map to avoid redundant calls.

Time
O(n)
Space
O(n)
function climbStairs(n) {
  const memo = new Map();
  function dp(k) {
    if (k <= 2) return k;
    if (memo.has(k)) return memo.get(k);
    const result = dp(k - 1) + dp(k - 2);
    memo.set(k, result);
    return result;
  }
  return dp(n);
}

Tradeoff: O(n) space for the memo and call stack. Correct but not the preferred answer when O(1) space is available.

DRW-specific tips

After the base solution, DRW interviewers frequently ask: 'Generalize — what if you can take 1, 2, or k steps?' (generalized Fibonacci: ways(n) = sum of ways(n-1) through ways(n-k)). Then: 'What if step sizes have costs and you want to minimize cost?' (weighted DP). This sequence mirrors lattice-path counting in binomial option pricing models — say so explicitly. Also: for very large n, mention matrix exponentiation to compute the nth Fibonacci in O(log n).

Common mistakes

  • Using an O(n) array for the DP table when only the last two values are needed.
  • Base case errors: ways(0) = 1 (empty path), ways(1) = 1, ways(2) = 2 — verify all three before coding.
  • Off-by-one: starting the loop at i=3 vs i=2 — trace through n=3 by hand.
  • Not recognizing the Fibonacci structure immediately — DRW will ask you to name the pattern.

Follow-up questions

An interviewer at DRW may pivot to one of these next:

  • Min Cost Climbing Stairs (LC 746) — each step has a cost; minimize total cost.
  • Generalize to k allowed step sizes — what is the recurrence and time complexity?
  • How does the number of paths grow as n → ∞, and what does that imply about lattice-based option pricing models?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is this a Fibonacci sequence?

ways(n) = ways(n-1) + ways(n-2) because the last step was either 1 or 2. The recurrence is identical to Fibonacci with shifted base cases.

Why does DRW care about the O(1) space version?

In high-frequency systems, DP tables for large n can cause cache pressure. Recognizing when you only need rolling state demonstrates systems-aware thinking.

What is the matrix-exponentiation approach?

Express [ways(n), ways(n-1)] = [[1,1],[1,0]]^n × [1,1]. Matrix exponentiation computes this in O(log n) — useful for astronomically large n.

Practice these live with InterviewChamp.AI

Drill Climbing Stairs and other DRW interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →