DP: Climbing Stairs
Easy+70 XPCount ways to climb n stairs (1 or 2 at a time) by filling a DP table.
No visualization loaded.
Watch
—
Press Run to begin.
Dynamic programming (DP) is recursion that stops repeating itself. To count the ways to climb n stairs taking 1 or 2 steps at a time, notice: the ways to reach stair n = ways to reach stair n-1 (then a 1-step) + ways to reach stair n-2 (then a 2-step). Instead of recomputing those over and over, you write each answer in a table once and reuse it. Fill the table bottom-up and the last cell is your answer.
▸What IS dynamic programming, in one idea?
Solve each smaller subproblem once, store its answer, and reuse it instead of recomputing. That's it. Plain recursion for this problem recomputes the same stairs again and again (exponential work); DP remembers, so each stair is computed a single time.
▸Why does ways(n) = ways(n-1) + ways(n-2)?
Your final move onto stair n is either a single step (from stair n-1) or a double step (from stair n-2) — those are the only options, and they don't overlap. So every way to reach n is one of those two cases added together. (That's the Fibonacci sequence, by the way!)
▸What's the 'DP table' the animation fills in?
A row of cells, one per stair, holding 'ways to reach this stair.' You seed the first couple by hand, then fill left to right: each cell = the two cells before it, summed. Because earlier cells are already filled, every new cell is instant. The last cell holds the final answer.
▸How is this different from the factorial recursion?
Factorial's calls never overlap — each is needed exactly once, so plain recursion is fine. Climbing stairs has HEAVY overlap (ways(3) is needed by both ways(4) and ways(5)), so recomputing is wasteful. DP shines precisely when subproblems repeat; the table is what kills the waste, turning exponential into O(n).
How the work grows
O(n) with DP is fair — grows in step with the data. Filling one table cell per stair is O(n) — a straight line. Without DP, plain recursion recomputes overlapping subproblems and balloons to O(2ⁿ) (the runaway curve). The table is what tames the explosion; it costs O(n) memory.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.