Dynamic Programming · Counting Ways
Climbing Stairs
You are climbing a staircase of n stairs. Each move, you take either 1 stair or 2. How many different ways can you reach the top? This is the gentlest place to meet dynamic programming, so we start here.
The ways to reach a stair are the ways to reach the two stairs below it, added together.
See it buildn = 5 stairs → 8 different ways to the top.
The Problem
Count the ways, do not list them
For a small staircase you could draw every route by hand: 1+1+1, 1+2, 2+1, and so on. That list explodes as the staircase grows. We want the count, and we want it without drawing a single route.
dp[i] is the number of different ways to reach stair i. Saying this in plain words first is the habit that makes every later step obvious.
The ground (stair 0)
You start here before climbing. There is exactly one way to be at the start: do nothing yet. So dp[0] = 1.
The first stair (stair 1)
Only one move reaches it: a single 1-stair step. There is no room for a 2-stair step yet. So dp[1] = 1.
The Key Idea
Every stair has exactly two ways in
Stand on any stair past the first. Your very last move was either a 1-stair step from the stair just below, or a 2-stair step from two stairs below. There is no third way to arrive. So the ways to reach this stair are simply the ways to reach those two stairs, added up.
Try It
Fill the strip, one stair at a time
Press play, or step through it by hand. Each cell is one stair. The two base cells are already filled; every cell after them is the sum of the two cells to its left.
Press play to start filling the strip
The amber ring marks the stair one below (a +1 move in); the teal ring marks the stair two below (a +2 move in).
The Result
The filled strip
For 5 stairs, the recurrence above produces this strip. The last cell is the answer: the number of ways to reach the top.
8 different ways to climb 5 stairs. The numbers are the Fibonacci sequence, which is no accident.
The Code
Same idea, two implementations
The array version keeps every stair's count. The two-variable version keeps only the last two counts, since that is all the recurrence ever looks at.
Complexity
What the optimization actually buys you
Array
Two variables
Get the plain array correct first. Compressing it to two variables is a second step, once you trust the recurrence.
Pattern To Remember
When the answer for step i is built from a fixed handful of earlier answers, you are looking at a one-dimensional recurrence.
dp[i] = combine(dp[i-1], dp[i-2], ...)
The same shape returns in Fibonacci, Min Cost Climbing Stairs, House Robber, Decode Ways, and Tribonacci. Next on the course: Min Cost Climbing Stairs, where each stair carries a price.