Skip to main content

70. Climbing Stairs

easyAsked at Akamai

Count the distinct ways to climb n stairs taking 1 or 2 steps at a time. Akamai uses this as an entry point into dynamic programming — the recurrence relation is immediately applicable to retry-strategy combinatorics and caching policy analysis.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2025-11)— Reported as a dynamic programming warm-up in Akamai university-hire interview loops.
  • Blind (2025-08)— Akamai new-grad threads mention Climbing Stairs as a first coding question before harder DP problems.

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. Dynamic programming (bottom-up)

dp[i] = number of ways to reach step i = dp[i-1] + dp[i-2]. Only the last two values are needed, so we can use two variables instead of an array.

Time
O(n)
Space
O(1)
function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1; // ways to reach step 1
  let prev1 = 2; // ways to reach step 2
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff: O(n) time, O(1) space. This is the Fibonacci recurrence. Mention the connection explicitly — Akamai interviewers appreciate recognizing canonical recurrences.

2. Memoized recursion (top-down)

Recurse from n down to base cases, caching results to avoid recomputation.

Time
O(n)
Space
O(n)
function climbStairs(n) {
  const memo = new Map();
  function dp(i) {
    if (i <= 2) return i;
    if (memo.has(i)) return memo.get(i);
    const result = dp(i - 1) + dp(i - 2);
    memo.set(i, result);
    return result;
  }
  return dp(n);
}

Tradeoff: More intuitive but uses O(n) stack and memo space. Useful if the interviewer wants to see recursive thinking before asking for the space-optimized version.

Akamai-specific tips

Start by deriving the recurrence: 'To land on step i, I either came from step i−1 (took 1 step) or step i−2 (took 2 steps) — so ways(i) = ways(i−1) + ways(i−2).' This is Fibonacci. Akamai interviewers like hearing the mathematical structure named, then seeing the O(1)-space optimization follow naturally.

Common mistakes

  • Returning 1 for n=2 instead of 2 — there are two ways to climb 2 steps: (1,1) or (2).
  • Using an O(n) array when only two values are needed — always offer the space-optimized version.
  • Naive recursion without memoization — exponential time, fails for n=45 within the constraint.

Follow-up questions

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

  • What if you can take 1, 2, or 3 steps? Generalize the recurrence.
  • How many ways if some steps are broken and cannot be landed on?
  • Decode Ways (LC 91) — a structurally similar DP on strings.

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 does this produce Fibonacci numbers?

The recurrence ways(n) = ways(n-1) + ways(n-2) with base cases ways(1)=1, ways(2)=2 generates the Fibonacci sequence offset by one index.

Is there a closed-form solution?

Yes — Binet's formula gives the nth Fibonacci number in O(1) arithmetic operations, but it involves floating-point which can lose precision for large n. For n <= 45 the iterative DP is simpler and exact.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →