Skip to main content

70. Climbing Stairs

easyAsked at Citadel

Climbing Stairs is Citadel's entry point for dynamic programming. The interviewer is checking whether you recognize the Fibonacci recurrence, state the subproblem clearly, and then optimize space from O(n) to O(1). Expect the question to pivot toward probability: 'What if each step choice is made with probability p?'

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

Source citations

Public interview reports confirming this problem appears in Citadel loops.

  • Glassdoor (2025-12)— Citadel SWE interview reports list Climbing Stairs as a canonical DP warm-up preceding harder DP questions in on-site rounds.
  • Blind (2025-10)— Citadel candidates note DP questions start easy (Climbing Stairs, Coin Change) and escalate within the same interview.

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. Bottom-up DP with array

Define dp[i] as the number of ways to reach step i. dp[i] = dp[i-1] + dp[i-2]. Base cases: dp[1] = 1, dp[2] = 2.

Time
O(n)
Space
O(n)
function climbStairs(n) {
  if (n <= 2) return n;
  const dp = new Array(n + 1);
  dp[1] = 1;
  dp[2] = 2;
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

Tradeoff: Clear and easy to reason about. O(n) space because we store the full dp array. Fine for n ≤ 45 but suboptimal — pivot to the two-variable approach when the interviewer asks for space optimization.

2. Space-optimized Fibonacci

You only ever need the previous two values. Replace the array with two variables.

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

Tradeoff: O(1) space. This is the expected final answer at Citadel. The variable-rolling technique generalizes to any fixed-window DP recurrence — knowing this pattern is essential.

Citadel-specific tips

State the recurrence before writing code: 'ways(n) = ways(n-1) + ways(n-2) because the last step is either a 1-step or a 2-step.' Citadel interviewers like to probe mathematical depth: 'This sequence is Fibonacci — what is the closed-form expression?' Know Binet's formula conceptually (involves the golden ratio φ). Also expect: 'What if you could take 1, 2, or 3 steps?' — this generalizes to dp[i] = dp[i-1] + dp[i-2] + dp[i-3], the tribonacci sequence.

Common mistakes

  • Not handling n = 1 separately — with one variable rolling you can get an off-by-one at small inputs.
  • Confusing the Fibonacci indexing — ways(1) = 1, ways(2) = 2, not ways(1) = 1, ways(2) = 1 (that's standard Fibonacci).
  • Starting the loop at i = 2 instead of i = 3 in the space-optimized version, causing an incorrect first iteration.
  • Memoizing with recursion but forgetting to initialize the memo structure — causes recomputation and defeats the purpose.

Follow-up questions

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

  • What if you can take 1, 2, or 3 steps? (Tribonacci generalization.)
  • What if each step has a cost and you want to minimize total cost? (LC 746, Min Cost Climbing Stairs.)
  • What is the expected number of steps if each choice is made uniformly at random?

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 equivalent to Fibonacci?

To reach step n you came from step n-1 (1-step) or step n-2 (2-step). This is the same recurrence as Fibonacci, just with different initial conditions.

Is the closed-form Fibonacci formula numerically stable?

No — floating-point errors in φ^n accumulate for large n. Use integer DP or matrix exponentiation for exact values.

How does this change if the stairs can be climbed in any order up to k steps?

dp[i] = sum of dp[i-j] for j = 1..k. Requires a sliding-window sum to maintain O(n) time rather than O(n*k).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →