70. Climbing Stairs
easyAsked at JPMorganCount 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 Sam K., 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
n = 22Explanation: 1+1 or 2.
Example 2
n = 33Explanation: 1+1+1, 1+2, 2+1.
Example 3
n = 58Approaches
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.
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.