#70 Climbing Stairs
frequently reported atAdobeInfosysBloombergAmazonMicrosoftGoogle
the problem
In plain words
You climb a staircase with n steps. Each move is 1 or 2 steps. In how many distinct ways can you reach the top?
in n = 2
out 2
1+1 or 2.
in n = 3
out 3
1+1+1, 1+2, 2+1.
- 1 ≤ n ≤ 45
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
pattern1D DP
Your last move was either 1 step (from n−1) or 2 steps (from n−2). So ways(n) = ways(n−1) + ways(n−2) — it's Fibonacci.
solutions
From brute force to optimal
Directly code ways(n) = ways(n−1) + ways(n−2).
- Base: n ≤ 1 → 1 way.
- Return ways(n−1) + ways(n−2).
Two calls per level, ~1.618ⁿ calls in total — n = 45 needs about 3.7 billion.
Recursion depth.
class Solution { public int climbStairs(int n) { if (n <= 1) return 1; // 0 or 1 step left: exactly one way return climbStairs(n - 1) + climbStairs(n - 2); // last move was 1 step or 2 steps }}Same recursion, but store ways(k) the first time.
- memo[k] = 0 means unknown (real answers are ≥ 1).
- Check memo before recursing; store after.
Each k from 2..n is computed once.
Memo array + recursion stack.
class Solution { public int climbStairs(int n) { return ways(n, new int[n + 1]); } private int ways(int n, int[] memo) { if (n <= 1) return 1; if (memo[n] != 0) return memo[n]; // already solved return memo[n] = ways(n - 1, memo) + ways(n - 2, memo); }}Fill dp[1..n] from the bottom up.
- dp[1] = 1, dp[2] = 2.
- dp[i] = dp[i−1] + dp[i−2] for i = 3..n.
- Return dp[n].
One loop, O(1) per step.
The table.
class Solution { public int climbStairs(int n) { if (n <= 2) return n; int[] dp = new int[n + 1]; // dp[i] = ways to reach step i dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }}Fill the table
Only the last two values are ever read — keep just those.
- prev2 = ways(0) = 1, prev1 = ways(1) = 1.
- Repeat: cur = prev1 + prev2, shift.
One loop.
Two ints.
class Solution { public int climbStairs(int n) { int prev2 = 1, prev1 = 1; // ways(0), ways(1) for (int i = 2; i <= n; i++) { int cur = prev1 + prev2; // last move: 1 step or 2 steps prev2 = prev1; prev1 = cur; } return prev1; }}Two variables, step by step
in the room
How to say it in the interview
talk track
- "Think about the last move: 1 step or 2. So ways(n) = ways(n−1) + ways(n−2)."
- Show the recursion, point out ways(n−2) is computed twice → memoize → table → two variables.
- Mention n = 45 gives 1,836,311,903, which still fits in an int.
traps
- Base cases: ways(0) = 1 (do nothing), not 0.
- Plain recursion times out for n around 40+.
what they ask next
Follow-ups
Min Cost Climbing Stairs (LC 746)?
The next problem: reach(i) = min(reach(i−1) + cost[i−1], reach(i−2) + cost[i−2]) — same two-variable shape, with min instead of +.
What if you can take 1, 2 or 3 steps (or any set of step sizes)?
ways(n) = Σ ways(n − s) over allowed sizes s. Same table; keep the last max(s) values.
before you submit
Edge cases to test
- n = 1 → 1 (a single step).
- n = 2 → 2 (1+1 or 2).
- n = 45 → 1,836,311,903: still fits in an int, but plain recursion needs about 3.7 billion calls.
practise next
Similar problems
- #746Min Cost Climbing StairsEasyin Dynamic Programming
- #509Fibonacci NumberEasyin Recursion
- #91Decode WaysMediumin Dynamic Programming