Skip to main content

28. Climbing Stairs

easyAsked at Expedia

Count distinct ways to climb n steps taking 1 or 2 at a time — Expedia uses this Fibonacci-DP warmup to probe how quickly candidates see the recurrence behind multi-stop trip combinations.

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

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 = 5
Output
8

Approaches

1. Recursive with memoization

ways(n) = ways(n-1) + ways(n-2). Cache results to avoid exponential recomputation.

Time
O(n)
Space
O(n)
function climbStairs(n) {
  const memo = new Map();

  function dp(i) {
    if (i <= 1) return 1;
    if (memo.has(i)) return memo.get(i);
    const result = dp(i - 1) + dp(i - 2);
    memo.set(i, result);
    return result;
  }

  return dp(n);
}

Tradeoff:

2. Iterative O(1) space (Fibonacci)

Keep only the previous two values. Recognize explicitly that this is Fibonacci and say so — the interviewer will note that.

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

Tradeoff:

Expedia-specific tips

Expedia uses this as a pacing question at the start of a loop. Nail it in under 5 minutes: name the Fibonacci recurrence, code the O(1) space iterative solution, and pre-empt the follow-up by noting the generalization to k-step variants — 'at most k steps per move' is a common extension their team uses for multi-leg booking flows.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →