LeetCode 70 ·
Easy
Climbing Stairs
Count the distinct ways to climb n stairs taking 1 or 2 steps at a time.
Try it
Step through the core mechanic. The simulator below runs the dynamic programming shape this problem is built on.
Interactive · Climbing Stairs — ways(n) ways(i) = ways(i−1) + ways(i−2)
| 1 | 1 | · | · | · | · | · |
0123456
base cases seeded
The approach
ways(n) = ways(n−1) + ways(n−2): the last move was a 1-step or a 2-step. Tabulate bottom-up keeping only the last two values for O(1) space.
| Aspect | Value |
|---|---|
| Pattern | Dynamic programming |
| Recognise it by | Ways to reach step n — Fibonacci recurrence. |
| Time complexity | O(n) |
| Space complexity | O(1) |
| Difficulty | Easy |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.