Skip to main content

70. Climbing Stairs

easyAsked at Anduril

Count the number of distinct ways to reach the top of a staircase taking 1 or 2 steps at a time. Anduril asks this to introduce dynamic programming thinking — recognizing that dp[n] = dp[n-1] + dp[n-2] is the same recurrence as Fibonacci, and seeing how memoization converts exponential recursion to linear time.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2025-11)— Reported in Anduril new-grad SWE screening threads as a DP introduction problem.
  • Blind (2025-07)— Climbing Stairs cited in early Anduril phone-screen prep threads as a Fibonacci-variant DP warm-up.

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. Recursive with memoization (top-down DP)

Define ways(n) = ways(n-1) + ways(n-2). Memoize to avoid recomputing subproblems.

Time
O(n)
Space
O(n)
function climbStairs(n) {
  const memo = new Map();
  function ways(k) {
    if (k <= 1) return 1;
    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: Illustrates memoization clearly but uses O(n) call-stack and O(n) memo space. Useful for explaining the recurrence.

2. Bottom-up DP (space-optimized)

Recognize that ways(n) only depends on the previous two values. Maintain two variables instead of a full array.

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

Tradeoff: O(1) space. This is the preferred answer at Anduril — it shows you can reduce the DP table once you spot that only two adjacent states matter, which is a key insight for memory-constrained embedded code.

Anduril-specific tips

Start by stating the recurrence: 'To reach step n, I either came from n-1 (one step) or n-2 (two steps), so ways(n) = ways(n-1) + ways(n-2).' Then immediately note it's the Fibonacci sequence. Anduril values engineers who spot structure and simplify — optimizing from O(n) space to O(1) by rolling two variables is exactly the kind of lean thinking they look for. Mention the pattern extends to k-step variants used in path-planning state machines.

Common mistakes

  • Returning n for the base case instead of 1 — ways(1)=1 and ways(2)=2 are the correct seeds.
  • Off-by-one in the bottom-up loop — starting the loop at i=3 when prev1 already holds the answer for n=2.
  • Using a full dp array of size n+1 when only two variables are needed.
  • Not recognizing this is Fibonacci — interviewers expect you to name the pattern.

Follow-up questions

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

  • Generalize to steps of size 1, 2, or 3 — how does the recurrence change?
  • What is the answer modulo 10^9+7 for very large n?
  • How would you enumerate the actual step sequences, not just count them?

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 ways(1) = 1 and ways(2) = 2?

For n=1 there is exactly one way: take a single step. For n=2 there are two ways: (1,1) or (2).

This is just Fibonacci — should I say that?

Yes. Naming the underlying structure shows pattern recognition that interviewers reward.

Does the naive recursion actually time out on LeetCode?

Not with n <= 45, but the exponential branching factor is 2^45 in the worst case without memoization — always memoize.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →