Skip to main content

70. Climbing Stairs

easyAsked at HP

Dynamic programming is central to HP's ink/toner optimization algorithms and cost-scheduling tools for enterprise print fleets. Climbing Stairs is the textbook DP entry point — HP uses it to confirm that candidates understand memoization and state transition before discussing more complex optimization problems.

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

Source citations

Public interview reports confirming this problem appears in HP loops.

  • Glassdoor (2025-Q4)— HP SWE interview reports cite Climbing Stairs as a common DP warm-up in phone and first onsite rounds.
  • Blind (2025-10)— HP interview prep discussions recommend practicing Climbing Stairs as a gateway to HP's DP question series.

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: There are two ways to climb to the top: (1 step + 1 step) or (2 steps).

Example 2

Input
n = 3
Output
3

Explanation: There are three ways: (1+1+1), (1+2), (2+1).

Approaches

1. Recursion with memoization (top-down DP)

Define ways(n) = ways(n-1) + ways(n-2). Cache results to avoid recomputation.

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

Tradeoff: Intuitive recursive structure. O(n) time with memoization, O(n) space for the cache plus call stack.

2. Fibonacci rolling variables (bottom-up, O(1) space)

Observe that ways(n) = Fibonacci(n+1). 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(1)
  let prev1 = 2; // ways(2)
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff: Optimal: O(n) time and O(1) space. No recursion overhead. This is the answer HP expects after you've established the DP recurrence.

HP-specific tips

State the recurrence relation explicitly before coding: 'To reach step n I could have come from step n-1 or step n-2, so ways(n) = ways(n-1) + ways(n-2).' HP interviewers reward structured thinking. Then show you can optimize from O(n) space to O(1) by observing only the last two values matter. Be ready to generalize to k-step climbing.

Common mistakes

  • Starting base cases at n=0 instead of n=1 — ways(0) = 1 (one way to stand at the bottom without moving) is valid but confusing; anchoring at n=1 and n=2 is clearer.
  • Allocating an O(n) array when two variables suffice.
  • Pure recursion without memoization — exponential time due to overlapping subproblems.
  • Off-by-one in the loop bounds when iterating from 3 to n.

Follow-up questions

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

  • Generalize to k steps at a time — how does the recurrence change?
  • What if certain steps are forbidden? How do you skip them in the DP?
  • What is the minimum cost to reach the top if each step has a cost (LC 746)?

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 the answer Fibonacci-like?

The recurrence ways(n) = ways(n-1) + ways(n-2) with base cases ways(1)=1, ways(2)=2 produces the Fibonacci sequence shifted by one index. This is a mathematical property, not a coincidence.

What is ways(1) and ways(2)?

ways(1) = 1 (only one way: take 1 step). ways(2) = 2 (either two 1-steps or one 2-step).

Can this problem be solved with matrix exponentiation?

Yes — the Fibonacci matrix exponentiation trick runs in O(log n) time, which matters for very large n. But for n ≤ 45 the linear solution is perfectly fine.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →