Practice: Climbing Stairs
Counting the ways.
You're climbing a staircase with N steps. Each time, you can climb one step, or two. How many different ways are there to reach the top? Pause. Think about the very last move.

- N steps
- Climb 1 or 2 at a time
- How many ways?
Thinking about the last move
To reach step N, your last move came from step N minus one, or step N minus two. So the ways to reach N are the ways to reach N minus one, plus the ways to reach N minus two. That's the same pattern as Fibonacci. We fill a table from the bottom. Run it. Ten steps can be climbed in eighty nine different ways.
def climb(n):
ways = [1, 1]
for i in range(2, n + 1):
ways.append(ways[i - 1] + ways[i - 2])
return ways[n]
for n in [1, 2, 3, 4, 10]:
print(n, "steps:", climb(n), "ways")1 steps: 1 ways 2 steps: 2 ways 3 steps: 3 ways 4 steps: 5 ways 10 steps: 89 ways
The DP recipe
Every dynamic programming problem follows the same recipe. Define what one entry in the table means. Here, the ways to reach step I. Find how it's built from smaller entries. Set the starting values. Then fill the table in order, and read off the answer.
| key | value |
|---|---|
| 1. Define | ways[i] = ways to reach step i |
| 2. Relate | ways[i-1] + ways[i-2] |
| 3. Start | ways[0] = ways[1] = 1 |
| 4. Fill | in order, read the answer |
Summary
The ways to climb N stairs equal the ways to N minus one, plus N minus two. Define, relate, start, and fill. Next, fixing the coin problem that greedy got wrong.
Key takeaways- Think about the last move
- Build from smaller answers
- Fill a table