Skip to main content

70. Climbing Stairs

easyAsked at Cisco

Climbing Stairs at Cisco is a 5-minute DP warm-up that filters for candidates who recognize the Fibonacci recurrence. The interviewer wants the O(1)-space bottom-up loop and is grading whether you go straight there or get stuck in naive recursion.

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

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco SDE-I phone screens cite Climbing Stairs as a recurring warm-up.
  • Levels.fyi (2025-12)— Cisco new-grad interview write-ups list this as a typical phone-screen round.

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. Naive recursion (exponential)

ways(n) = ways(n-1) + ways(n-2). Base cases: ways(1) = 1, ways(2) = 2.

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

Tradeoff: Recomputes the same subproblems exponentially. Times out on n=45 (would take seconds). Useful only to show you see the recurrence — Cisco interviewers will push you to memoize immediately.

2. Memoized recursion (top-down DP)

Same recurrence, cached by n.

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

Tradeoff: Linear time, linear space. Recursion stack adds O(n) more space on top of the memo. Cisco interviewers accept this but want the iterative O(1)-space version below.

3. Bottom-up DP with two variables (optimal)

Iterate from 1 to n, maintaining only the previous 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 cur = prev1 + prev2;
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

Tradeoff: The canonical answer. Linear time, constant space, no recursion. State out loud 'I only need the previous two values, not the whole array' — that earns the interview signal.

Cisco-specific tips

Cisco interviewers grade this in 5 minutes. State the recurrence FIRST: 'To reach step n, you either took a single step from n-1 or a double step from n-2 — so ways(n) = ways(n-1) + ways(n-2). That's Fibonacci.' Then write the O(1)-space iterative version. Anyone who writes plain recursion or even memoized recursion has cost themselves the easy yes.

Common mistakes

  • Off-by-one: confusing ways(1) and ways(2). ways(1) = 1, ways(2) = 2.
  • Plain recursion without memoization — TLEs on n=45.
  • Allocating an O(n) dp[] array when two scalars suffice.

Follow-up questions

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

  • Min Cost Climbing Stairs (LC 746) — costs at each step; minimize total.
  • What if you can take 1, 2, or 3 steps? (ways(n) = ways(n-1) + ways(n-2) + ways(n-3).)
  • What if you can take steps of any size in a set S? (Coin Change style DP.)
  • Decode Ways (LC 91) — another Fibonacci-ish DP with conditional transitions.

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 'really' Fibonacci?

Because the recurrence ways(n) = ways(n-1) + ways(n-2) with ways(1) = 1, ways(2) = 2 produces the sequence 1, 2, 3, 5, 8, 13... which is the Fibonacci numbers shifted by one. The matrix-exponentiation O(log n) trick from Fibonacci applies here too as a bonus follow-up.

Is the O(log n) matrix-exponentiation version expected?

Only as a follow-up — if the interviewer says 'what if n could be 10^18?' you mention 'matrix exponentiation of [[1,1],[1,0]]^n in O(log n).' For the standard n=45 constraint, the O(n) loop is the expected answer.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →