Skip to main content

17. Climbing Stairs

easyAsked at Roblox

Count distinct ways to reach the top taking 1 or 2 steps at a time — Roblox references this DP warmup when discussing how the engine enumerates valid move combinations for character pathfinding constraints.

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

Problem

You are climbing a staircase with n steps. Each time you can either climb 1 or 2 steps. Return the number of distinct ways to reach 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. Brute force — recursion

Recursively sum ways(n-1) + ways(n-2), recomputing overlapping sub-problems. Exponential time.

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. Optimal — constant-space DP

Recognize the recurrence is Fibonacci. Keep only the previous two values, iterating bottom-up in O(n) time and O(1) space.

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:

Roblox-specific tips

Roblox uses this to test whether you recognize Fibonacci patterns and can eliminate memoization overhead entirely. They'll push you to generalize: what if a character can jump 1, 2, or 3 steps? That immediately extends to a sliding-window DP sum — know how to adapt the recurrence on the spot.

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

Practice these live with InterviewChamp.AI →