70. Climbing Stairs
easyAsked at CiscoClimbing 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 Sam K., 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
n = 22Explanation: Two ways: 1+1 or 2.
Example 2
n = 33Explanation: 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.
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.