Climbing Stairs
Bottom-up table fill — the canonical first DP
Every path that reaches step i has to end with one specific last move — a single step up from i-1, or a double step up from i-2 — and those two cases cover every possibility with no overlap, so the count for step i is simply the count for i-1 plus the count for i-2. Instead of recursing top-down and re-solving the same stairs over and over, fill a table bottom-up so dp[i-1] and dp[i-2] are already final by the time dp[i] needs them.
Details
Animated on: Climbing Stairs: you can climb 1 or 2 steps at a time — how many distinct ways to reach the top of n = 6 stairs?
Problem:Climbing StairsEasy
Pattern:1D Dynamic Programming
Bottom-up table fill — the canonical first DP
step 1 / 10
n = 6 stairs. Build a table dp[0..6] where dp[i] = number of distinct ways to reach step i. Bottom-up DP: solve the tiny cases first, then combine them upward.
1FUNCTION climbStairs(n):2 dp = a table of size n + 13 dp[0] = 1, dp[1] = 14 FOR i from 2 to n:5 dp[i] = dp[i-1] + dp[i-2]6 RETURN dp[n]
← / → step · space play · Home restart
Every step in words
Show all 10 steps
- n = 6 stairs. Build a table dp[0..6] where dp[i] = number of distinct ways to reach step i. Bottom-up DP: solve the tiny cases first, then combine them upward.
- Base cases: dp[0] = 1 (stand at the bottom — one way: do nothing) and dp[1] = 1 (a single 1-step). Every later cell is built from these two.
- i = 2. The LAST move onto step 2 was either a 1-step from step 1 or a 2-step from step 0 — no other way to land here. The two groups are disjoint and cover everything, so ADD them: dp[1] + dp[0] = 1 + 1.
- dp[2] = 2. Sanity check: the two ways are 1+1 and 2. The subproblem answers we reused were already final — that is exactly why we fill in bottom-up order.
- i = 3. Same recurrence, one step higher: arrive from step 2 (+1) or step 1 (+2). Read the table, don't recompute: dp[2] + dp[1] = 2 + 1.
- dp[3] = 3: the ways are 1+1+1, 1+2, 2+1. Each new cell only ever reads the two cells behind it — O(1) work per stair.
- i = 4: dp[3] + dp[2] = 3 + 2 = 5. The Fibonacci shape emerges — each entry is the sum of the previous two, because every climb ends in a 1-step or a 2-step.
- i = 5: dp[4] + dp[3] = 5 + 3 = 8. Naive recursion would re-solve these subproblems exponentially many times; the table computes each exactly once — that is the whole point of DP.
- i = 6, the top: dp[5] + dp[4] = 8 + 5 = 13. The table is full — n cells filled, O(1) each.
- Answer: dp[6] = 13 distinct ways to climb 6 stairs. O(n) time, O(n) space — and since each cell reads only the two behind it, two variables would even shrink space to O(1).
Now solve it yourself
Watching is the first half. The second is writing it without the animation.