Skip to main content

70. Climbing Stairs

easyAsked at Intel

You can climb 1 or 2 stairs at a time; how many distinct ways to reach the top? Intel uses this as the entry point to DP discussion — the recurrence is Fibonacci-shaped and the interviewer is checking whether you spot it before you write three nested loops.

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

Source citations

Public interview reports confirming this problem appears in Intel loops.

  • Glassdoor (2026-Q1)— Intel SWE phone-screen reports cite climbing-stairs as a recurring DP warm-up.
  • GeeksforGeeks (2025-09)— Intel Interview Experience archives include climbing-stairs as a 'must-know DP introduction'.
  • LeetCode discuss (2025-11)— Intel-tagged in the company-frequency listing.

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: There are 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 (brute)

ways(n) = ways(n-1) + ways(n-2). Direct translation.

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

Tradeoff: Exponential — same overlapping-subproblem issue as naive Fibonacci. For n = 45 (the constraint cap), this is ~10^13 calls; times out instantly.

2. Iterative DP (optimal)

Track only the last two values. ways[i] = ways[i-1] + ways[i-2].

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

Tradeoff: Linear time, constant space. The canonical ship. Identical structure to iterative Fibonacci — pointing this out (this IS Fibonacci shifted by 1) is the senior signal.

Intel-specific tips

Intel interviewers will press 'can you do better than O(n)?' once you ship the iterative version. The answer is matrix exponentiation O(log n) — same as Fibonacci. If you've already written the matrix-exp Fibonacci solution, you can reuse it verbatim. Recognizing 'this problem IS Fibonacci' upfront and saying so is what Intel grades — not just producing a correct answer.

Common mistakes

  • Confusing the base case: ways(0) is undefined for this problem; ways(1) = 1; ways(2) = 2. Off-by-one in initialization yields a shifted sequence.
  • Pre-allocating a full dp[n+1] array — works but wastes O(n) space. Two variables suffice.
  • Not recognizing the Fibonacci shape and writing a 2D dp[i][last_step] table — over-engineered for this problem.

Follow-up questions

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

  • Climbing Stairs with k steps (LC 746 variants) — generalize to ways(n) = sum(ways(n-i)) for i in 1..k.
  • Min Cost Climbing Stairs (LC 746) — same recurrence shape with a cost array.
  • What if you could climb 1 OR 3 OR 5? (Same DP, recurrence over the allowed step set.)

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

F(n) = F(n-1) + F(n-2) with F(1)=1, F(2)=2 is exactly Fibonacci shifted by one index. ways(n) corresponds to F(n+1) in the standard Fibonacci indexing.

Do I need a full dp array?

No. Each step only needs the previous two values, so two integer variables suffice. The full array is useful only if you also need to print or backtrack the path.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →