Skip to main content

70. Climbing Stairs

easyAsked at Broadcom

Count the number of ways to climb n stairs taking 1 or 2 steps at a time. Broadcom uses this as an entry point to dynamic programming — the same recurrence structure appears in firmware retry-path enumeration and error-correction code design.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2025-11)— Mentioned in Broadcom new-grad interview reports as a dynamic programming baseline question.
  • Blind (2025-07)— Broadcom software infrastructure threads list Climbing Stairs as a warm-up before harder DP problems.

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 (for exposition)

f(n) = f(n-1) + f(n-2). Base cases: f(1)=1, f(2)=2. Exponential time due to overlapping sub-problems.

Time
O(2^n)
Space
O(n) call stack
function climbStairs(n) {
  if (n <= 2) return n;
  return climbStairs(n - 1) + climbStairs(n - 2);
}

Tradeoff: Illustrates the recurrence but is too slow. Use it only to derive the DP transition.

2. Bottom-up DP (space-optimised)

Since f(n) depends only on the last two values, maintain two variables instead of a full DP array.

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 curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff: O(n) time, O(1) space. Identical to computing Fibonacci with the same optimisation. Broadcom interviewers expect you to name the Fibonacci connection and explain the space reduction.

Broadcom-specific tips

Name the Fibonacci connection immediately: 'The recurrence f(n) = f(n-1) + f(n-2) is Fibonacci shifted by one — I can compute it in O(1) space by keeping only the last two values.' Broadcom values concise DP thinking. Follow up by noting that this same recurrence governs multi-hop path enumeration in ECMP routing tables, which is relevant to Broadcom's switching ASIC work.

Common mistakes

  • Returning n instead of n for base cases — f(1)=1, f(2)=2 are both correct; be precise.
  • Allocating an O(n) DP array when two variables suffice — Broadcom notices unnecessary memory allocation.
  • Not recognising the Fibonacci pattern — naming it signals DP fluency.
  • Off-by-one in the loop boundary — starting from i=3 up to and including n.

Follow-up questions

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

  • What if you can take 1, 2, or 3 steps at a time?
  • What if certain steps are broken and cannot be used?
  • How do you count paths with at most k consecutive 2-steps?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Is this exactly Fibonacci?

Yes, shifted by one index. climbStairs(n) = Fibonacci(n+1) using the standard Fibonacci sequence starting F(1)=1, F(2)=1.

Can I solve this with matrix exponentiation for very large n?

Yes — matrix exponentiation gives O(log n) time. Mention it if asked about extremely large n beyond the constraint.

Why does Broadcom ask DP warm-up questions?

Infrastructure software roles at Broadcom involve path enumeration and resource-allocation optimisation. DP fluency is a core signal.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →