Skip to main content

8. Climbing Stairs

easyAsked at Grab

Count distinct ways to climb n stairs taking 1 or 2 steps — a Grab warm-up for DP fluency.

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

Problem

You are climbing a staircase that takes n steps to reach the top. Each time you can climb 1 or 2 steps. Return how many distinct ways you can climb to the top.

Constraints

  • 1 <= n <= 45

Examples

Example 1

Input
n = 2
Output
2

Example 2

Input
n = 3
Output
3

Approaches

1. Brute force recursion

Recurse on f(n-1) + f(n-2).

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

Tradeoff:

2. Bottom-up DP

Track two prior values; iterate forward in O(n) time and O(1) space.

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

Tradeoff:

Grab-specific tips

Grab interviewers like candidates who recognize the Fibonacci shape immediately and frame it as a ride-stage counting problem on their SEA super-app.

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

Practice these live with InterviewChamp.AI →