DP — Climbing Stairs
↗ LeetCode: Climbing Stairs · Easy · pattern chapter →
Asked atMetaAmazonGoogleAdobeBloomberg
Steps of 1 or 2. Number of ways to reach step n.
Example 1 — n=2 → 2Example 2 — n=3 → 3
Constraints — 1 ≤ n ≤ 45. Brute recursion is O(2ⁿ) — at n=45 that's ~3.5·10¹³ ops (dies past a full year at 10⁶ ops/sec). Rolling 2-variable DP is O(n) = 45 additions.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Recursion + memo
O(n).
Approach 2 — Bottom-up DP O(1) space (canonical)
Insight. dp[i] = dp[i-1] + dp[i-2] — Fibonacci.
java
int climbStairs(int n) {
int a = 1, b = 1;
for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; }
return b;
}Approach 3 — Matrix exponentiation
[[1,1],[1,0]]^n → O(log n). Interview curiosity.
Complexity — Time O(n) DP; Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Memo | O(n) | O(n) | correct |
| Rolling DP | O(n) | O(1) | canonical |
| Matrix expo | O(log n) | O(1) | polish |
When to use which
- Standard → rolling DP.
- Very large n → matrix expo or closed-form Binet.
- Steps of {1..k} → same recurrence extended.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems