Skip to main content

70. Climbing Stairs

easyAsked at Hugging Face

Count the distinct ways to climb n stairs taking 1 or 2 steps at a time. Hugging Face uses this as a gateway to dynamic programming — the same recurrence thinking that underlies sequence-to-sequence decoding where each output token depends on a bounded window of prior states.

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

Source citations

Public interview reports confirming this problem appears in Hugging Face loops.

  • Glassdoor (2026-Q1)— Cited in Hugging Face early-round coding reports as a DP warm-up to assess recurrence reasoning.
  • Blind (2025-10)— Hugging Face interview threads list Climbing Stairs alongside Fibonacci as a baseline DP check.

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+1) or (2).

Example 2

Input
n = 3
Output
3

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

Approaches

1. Memoized recursion (top-down DP)

Recursive helper with a cache. ways(n) = ways(n-1) + ways(n-2), base cases ways(1)=1, ways(2)=2.

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

Tradeoff: Intuitive structure that mirrors the recurrence. O(n) time after memoization, O(n) space for the cache and call stack.

2. Iterative bottom-up DP (space-optimized)

Since each step depends only on the previous two, maintain just two variables. Equivalent to computing the Fibonacci sequence.

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(1) space — the preferred production answer. Mention this is the Fibonacci recurrence and that the same rolling-window trick applies to any DP whose state depends on a fixed number of prior values.

Hugging Face-specific tips

Hugging Face expects you to identify the recurrence before coding: 'To reach step n I must have come from n-1 or n-2, so ways(n) = ways(n-1) + ways(n-2).' Then optimize space. Connect it to sequence modeling: 'This is analogous to how autoregressive decoding computes the next token distribution based on a fixed-size context window — each step depends only on a bounded set of prior states.'

Common mistakes

  • Off-by-one errors — make sure base cases cover n=1 (return 1) and n=2 (return 2).
  • Exponential recursion without memoization — naive recursion is O(2^n) and TLEs on n=45.
  • Using an O(n) array for DP when only two variables are needed.
  • Confusing ways(0)=1 vs ways(1)=1 base cases — pick one convention and stay consistent.

Follow-up questions

An interviewer at Hugging Face may pivot to one of these next:

  • Min Cost Climbing Stairs (LC 746) — attach a cost to each step and minimize total cost.
  • What if you could take up to k steps at a time? The recurrence becomes ways(n) = sum of ways(n-1)...ways(n-k).
  • How would you handle this if n could be 10^9? (Matrix exponentiation reduces it to O(log n).)

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 the same as Fibonacci?

The recurrence f(n) = f(n-1) + f(n-2) is identical to Fibonacci, just with different base cases (here f(1)=1, f(2)=2 instead of f(0)=0, f(1)=1).

Does memoization or tabulation matter here?

Both are O(n) time. Tabulation (bottom-up) avoids call stack overhead, so it's preferred for large n or in languages with strict stack limits.

Can this overflow for n=45?

No — f(45) = 1,836,311,903 which fits in a 32-bit integer. No BigInt needed.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →