Skip to main content

70. Climbing Stairs

easyAsked at Linear

Count the number of distinct ways to climb n stairs taking 1 or 2 steps at a time. Linear asks this to see if you recognize it as Fibonacci DP and can articulate why memoization beats plain recursion — a proxy for how you think about repeated subproblems.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2025-11)— Mentioned in Linear new-grad phone screen reports as a DP warm-up.
  • Blind (2025-10)— Cited in Linear SWE interview threads as an introductory dynamic programming question.

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: Two ways: (1 step + 1 step) or (2 steps).

Example 2

Input
n = 3
Output
3

Explanation: Three ways: (1+1+1), (1+2), (2+1).

Approaches

1. Naive recursion

Recursively compute ways(n) = ways(n-1) + ways(n-2). Exponential due to overlapping subproblems.

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

Tradeoff: Correct but exponentially slow. Only show this to name the overlapping-subproblems problem before memoizing.

2. Bottom-up DP (Fibonacci iteration)

Build up from the base cases, keeping only the last two values.

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. The recurrence ways(n) = ways(n-1) + ways(n-2) is exactly the Fibonacci sequence shifted by 1. Name this connection — Linear interviewers reward pattern recognition.

Linear-specific tips

When you recognize the Fibonacci structure, say it out loud: 'The recurrence here is identical to Fibonacci — the number of ways to reach step n equals the sum of ways to reach n-1 and n-2.' Linear values communicating the 'why' behind a solution, not just the code.

Common mistakes

  • Using an O(n) DP array when two variables suffice — always ask yourself if the recurrence only needs the last k values.
  • Off-by-one on the base cases — ways(1) = 1, ways(2) = 2, not ways(0) = 0.
  • Not naming the Fibonacci connection — interviewers specifically look for this insight.

Follow-up questions

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

  • Min Cost Climbing Stairs (LC 746) — DP with a cost attached to each step.
  • What if you can take 1, 2, or 3 steps? (Generalizes the recurrence to 3 terms.)
  • How would you solve this for very large n where the result overflows a 32-bit integer?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Is this really just Fibonacci?

Yes — shifted by one. climbStairs(1)=1, climbStairs(2)=2, climbStairs(3)=3, climbStairs(4)=5... that's fib(2), fib(3), fib(4), fib(5). Name this; interviewers love it.

Why does dp[n] = dp[n-1] + dp[n-2]?

The last step must be either 1 step (leaving n-1 steps) or 2 steps (leaving n-2 steps). Sum the two sub-counts — that's the complete enumeration.

Can I use memoization instead of bottom-up?

Yes, top-down with a cache gives O(n) time and O(n) space. Bottom-up with two variables is optimal at O(1) space.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →