Climbing Stairs
Count the ways to climb n stairs — the gentlest introduction to dynamic programming
Problem Statement
You are climbing a staircase with n steps. Each time you may climb 1 step or 2 steps. How many distinct ways can you reach the top?
Input: n = 2
Output: 2
Ways: 1+1, 2
Input: n = 3
Output: 3
Ways: 1+1+1, 1+2, 2+1
Input: n = 4
Output: 5
Ways: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2Intuition
Enumerating every path works for n = 4 and becomes hopeless by n = 40. The way in is to think backwards from the destination.
The key insight
To be standing on step n, your final move was either a 1-step or a 2-step. There is no third option. So:
- You were on step
n - 1and took 1 step, or - You were on step
n - 2and took 2 steps
Those two groups are disjoint (they differ in the last move) and together they cover everything. Therefore:
ways(n) = ways(n - 1) + ways(n - 2)
That is the Fibonacci recurrence. With base cases ways(1) = 1 and ways(2) = 2, the sequence runs 1, 2, 3, 5, 8, 13, ….
Why the naive recursion is unusable
Writing the recurrence directly recomputes the same values astronomically often:
f(5)
┌───────┴───────┐
f(4) f(3)
┌────┴────┐ ┌────┴────┐
f(3) f(2) f(2) f(1)
┌───┴───┐
f(2) f(1)f(3) is computed twice, f(2) three times. The tree roughly doubles at each level, giving O(2ⁿ) — for n = 45 that is over a trillion calls.
This is exactly what dynamic programming fixes
The subproblems overlap. Compute each one once and reuse the answer:
- Top-down (memoization) — keep the recursion, cache results in a dictionary.
- Bottom-up (tabulation) — start from the base cases and build upward in a loop.
Either turns O(2ⁿ) into O(n).
Watch it run
Solution
Bottom-up with two variables
Since ways(n) needs only the previous two values, the whole table collapses to two numbers.
def climb_stairs(n: int) -> int:
"""Number of distinct ways to climb n stairs taking 1 or 2 at a time."""
if n <= 2:
return n
prev, curr = 1, 2 # ways to reach step 1 and step 2
for _ in range(3, n + 1):
prev, curr = curr, prev + curr
return currTop-down with memoization
Closer to how you would first think about the problem, and useful when the recurrence is harder to unroll into a loop.
from functools import lru_cache
def climb_stairs_memo(n: int) -> int:
@lru_cache(maxsize=None)
def ways(step: int) -> int:
if step <= 2:
return step
return ways(step - 1) + ways(step - 2)
return ways(n)Watch the base cases
ways(1) = 1 and ways(2) = 2 — not the usual Fibonacci 1, 1. This sequence is Fibonacci shifted by one position. Getting the base cases wrong produces answers that are off by exactly one Fibonacci index, which is easy to miss on small tests.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
| Approach | Time | Space |
|---|---|---|
| Naive recursion | O(2ⁿ) | O(n) |
| Memoization | O(n) | O(n) |
| Tabulation (array) | O(n) | O(n) |
| Two variables | O(n) | O(1) |
The jump from O(2ⁿ) to O(n) is what dynamic programming buys. Dropping to O(1) space is a bonus available whenever a recurrence looks back a fixed number of steps.
Recognising a DP Problem
Climbing Stairs is the smallest problem that shows both required properties:
- Optimal substructure — the answer for
nis built from answers for smaller inputs. - Overlapping subproblems — the same smaller inputs are needed repeatedly.
Property 2 is what separates DP from plain divide-and-conquer. Merge sort has property 1 but its halves never overlap, so caching would buy nothing.
Edge Cases
Related Problems
- Best Time to Buy and Sell Stock — DP whose table also collapses to a couple of variables
- Jump Game — solvable by DP, but greedy does it in
O(n)with less thinking - Min Stack — carrying computed state forward instead of recomputing