Climbing stairs: remember, don't repeat
You climb a staircase one or two steps at a time. In how many different ways can you reach the top? Build the answer up stair by stair from the answers before it, and see why remembering answers beats working them out again and again.
Core concept
Dynamic programming solves a big problem from the answers to smaller ones and remembers them: the ways to climb n stairs are the ways for n − 1 plus the ways for n − 2
Topic: Algorithm efficiency
Suppose you can climb a staircase one stair or two stairs at a time. One stair can be climbed in 1 way, two stairs in 2 ways (1 + 1, or 2). For any bigger staircase, your last move was either one stair, from n − 1, or two stairs, from n − 2. So the ways for n stairs are the ways for n − 1 plus the ways for n − 2. A simple recursive program would work out the smaller answers again and again, millions of times for a tall staircase. Dynamic programming is smarter: it starts from the bottom, works out each answer once, and remembers it. This program remembers just the last two answers, prev and ways, and builds up one stair at a time.
What you will learn
- Explain why ways(n) = ways(n − 1) + ways(n − 2).
- Trace the bottom-up loop with prev, ways and next.
- Explain why remembering answers saves work.
- Order the lines that update the two remembered answers.
Before you start
- Know how a for loop and variables work.
Materials
- A notebook to list the ways for 1, 2, 3 and 4 stairs by hand
Equipment
- None
Procedure
- Run the program for 5 stairs and read the ways for each stair.
- Step through it and watch prev and ways move up.
- Try 10 stairs.
- Answer the practice challenges.