Skip to main content

70. Climbing Stairs

easyAsked at JPMorgan

Count the distinct ways to climb n stairs, taking 1 or 2 steps at a time. JPMorgan asks this on Software Engineer Programme phone screens as the simplest dynamic-programming problem — your willingness to recognise the Fibonacci recurrence is the grading signal.

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

Source citations

Public interview reports confirming this problem appears in JPMorgan loops.

  • Glassdoor (2026-Q1)— Repeated in JPMorgan Software Engineer Programme phone-screen reports.
  • LeetCode (2026-Q1)— Tagged JPMorgan on the LeetCode company tag page.
  • Blind (2025-12)— JPMC SWE-I write-up: 'phone screen — climbing stairs, then asked to extend to k steps'.

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: 1+1 or 2.

Example 2

Input
n = 3
Output
3

Explanation: 1+1+1, 1+2, 2+1.

Example 3

Input
n = 5
Output
8

Approaches

1. Naive recursion (exponential — for understanding)

f(n) = f(n-1) + f(n-2) directly, with base cases f(1)=1, f(2)=2.

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

Tradeoff: Trivially correct but exponential — TLEs at the n=45 upper bound. Useful only to motivate the memoised version.

2. Bottom-up DP with O(1) rolling variables (optimal)

Compute f(n) = f(n-1) + f(n-2) iteratively, keeping only the last two values.

Time
O(n)
Space
O(1)
function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1;
  let prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const cur = prev1 + prev2;
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

Tradeoff: O(n) time, O(1) space. The two-variable rolling pattern is the same one you see in Fibonacci — recognising the equivalence on a phone screen is the highest-value signal you can send.

3. Closed-form using golden ratio

Climbing Stairs is the Fibonacci sequence offset by one. Use Binet's formula.

Time
O(1) (assuming O(1) pow)
Space
O(1)
function climbStairsClosed(n) {
  const phi = (1 + Math.sqrt(5)) / 2;
  const psi = (1 - Math.sqrt(5)) / 2;
  return Math.round((Math.pow(phi, n + 1) - Math.pow(psi, n + 1)) / Math.sqrt(5));
}

Tradeoff: O(1) time in theory but loses precision for large n because of floating-point error. JPMorgan interviewers will accept it as a curiosity but expect the rolling-DP answer as the primary.

JPMorgan-specific tips

JPMorgan interviewers grade the dynamic-programming reflex. The strongest answer in 60 seconds is: 'I notice f(n) = f(n-1) + f(n-2) — this is Fibonacci. I will write it bottom-up with two rolling variables for O(n) time and O(1) space.' Then write 8 lines of code. If you only do the recursive version, expect a 'how would you make it O(n)?' follow-up — better to volunteer the optimisation.

Common mistakes

  • Off-by-one on base case: f(1) = 1, f(2) = 2 — many candidates write f(2) = 1.
  • Memoising into a global object without resetting between calls — wrong on test harnesses that reuse the function.
  • Using recursion without memoisation and then hitting TLE on n=45.
  • Forgetting that the closed-form has precision issues — answers diverge from the DP for large n.

Follow-up questions

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

  • What if you can take 1, 2, or 3 steps?
  • What if each step has a cost and you want minimum total cost? (LC 746.)
  • What if there are forbidden steps you cannot land on?
  • Climbing Stairs in O(log n) with matrix exponentiation.

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

The last move is either a 1-step (so the prefix is a valid sequence to n-1) or a 2-step (so the prefix is a valid sequence to n-2). The total count is therefore f(n-1) + f(n-2). The base cases align with f(1)=1 and f(2)=2, which is Fibonacci shifted by one.

Should I memoise the recursive version or write the iterative one?

Write iterative. Memoised recursion is O(n) time but uses O(n) stack and O(n) memo space; the two-variable iterative version is the same time, O(1) space, and easier to explain to the interviewer.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →