Skip to main content

18. Climbing Stairs

easyAsked at Tesla

Count distinct ways to climb n steps taking 1 or 2 at a time — Tesla uses this DP foundation to reason about battery-mode transition sequences where each energy state can shift by one or two regeneration levels.

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

Problem

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. Return the number of distinct ways to reach the top.

Constraints

  • 1 <= n <= 45

Examples

Example 1

Input
n = 3
Output
3

Explanation: Three ways: (1+1+1), (1+2), (2+1).

Example 2

Input
n = 5
Output
8

Approaches

1. Naive recursion

Recursively compute ways(n) = ways(n-1) + ways(n-2). Exponential due to overlapping sub-problems.

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

Tradeoff:

2. Bottom-up DP (space-optimized)

Fibonacci recurrence iterated forward with two variables. Constant space, linear time.

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

Tradeoff:

Tesla-specific tips

Tesla uses this as a DP entry gate — the question itself is simple, but they grade on how fast you recognize the Fibonacci structure and how clearly you explain why the recursive tree has redundant nodes. Mention memoization as a stepping stone before jumping to the O(1)-space bottom-up form. They often follow up: 'What if you could take 1, 2, or 3 steps?' — generalize the recurrence on the whiteboard before they ask.

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 Tesla interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →