Skip to main content

70. Climbing Stairs

easyAsked at AMD

Count the distinct ways to climb n stairs taking 1 or 2 steps at a time. AMD uses this classic DP entry point to check whether candidates recognize overlapping subproblems and memoize — essential thinking for optimization passes in compilers and GPU shader pipelines.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2025-12)— AMD new-grad phone screens include Climbing Stairs as a DP warm-up to check memoization intuition.
  • Blind (2025-08)— AMD interview prep threads list this as a common easy DP problem in first-round coding.

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. Recursive with memoization (top-down DP)

climbStairs(n) = climbStairs(n-1) + climbStairs(n-2). Cache results to avoid recomputing.

Time
O(n)
Space
O(n)
function climbStairs(n) {
  const memo = {};
  function dp(i) {
    if (i <= 1) return 1;
    if (memo[i] !== undefined) return memo[i];
    memo[i] = dp(i - 1) + dp(i - 2);
    return memo[i];
  }
  return dp(n);
}

Tradeoff: Intuitive for candidates who think recursively. O(n) after memoization but uses O(n) call stack + cache.

2. Bottom-up DP (space-optimized)

Recognize that only the previous two values matter. Use two variables instead of a full 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(1) space. Preferred at AMD where register-pressure and memory efficiency are first-class concerns. This is the Fibonacci sequence with a sliding window.

AMD-specific tips

AMD engineers optimize loops for register use and pipeline depth. The space-optimized two-variable approach maps directly to that mindset: instead of storing an array (cache lines), you keep only two live values (two registers). Name the connection explicitly: 'I only need the two most recent values, so I can keep them in two variables — no array needed.' This shows low-level efficiency intuition AMD values.

Common mistakes

  • Naive recursion without memoization — exponential time, will TLE for n=45.
  • Initializing the DP array incorrectly — dp[0]=1 (one way to be at the base) and dp[1]=1 (one step).
  • Off-by-one errors in the loop bounds — start the loop at i=3 when using two variables initialized to dp[1]=1, dp[2]=2.
  • Returning n for the base case instead of correctly handling n=1 and n=2 separately.

Follow-up questions

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

  • What if you can take 1, 2, or 3 steps? (Generalize the recurrence.)
  • Decode Ways (LC 91) — a direct extension with variable step encoding.
  • How does memoization relate to instruction-level caching in a processor pipeline?

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

Because each state depends on exactly the two previous states: f(n) = f(n-1) + f(n-2). The base cases differ (f(1)=1, f(2)=2 vs Fibonacci's f(1)=1, f(2)=1) but the recurrence is identical.

Is the space-optimized O(1) version always better?

In practice yes — it uses two registers instead of an O(n) array. The only downside is you lose the ability to reconstruct the path, but this problem only asks for the count.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →