Dynamic Programming
Solve complex problems by breaking them into overlapping subproblems
This concept builds on Recursion — Functions That Call Themselves, Graph Traversal. Consider exploring them first for the best experience.
Spot the Repeated Work
Click 'Recursion tree' to see what plain recursion does. Every circle is one call, and each fib(k) calls fib(k−1) and fib(k−2). The orange circles are fib(3): it is computed three separate times inside fib(6), and the red circles mark the other repeats. That duplicated effort is the overlapping-subproblem signal dynamic programming exploits.
Start from the Base Cases
Click 'Table' to switch back. Cells [0] and [1] hold the base cases fib(0) = 0 and fib(1) = 1, so nothing needs computing. Press 'Next cell' to fill exactly one more cell and pause, so you can check each value before moving on. The yellow cell is the one being filled.
Each Cell Reuses Two Neighbours
Watch the blue arrows: every new cell adds the two cells to its left, and the formula line under the bars spells out the sum, such as fib(4) = fib(3) + fib(2) = 2 + 1 = 3. Each value is computed once, stored, then looked up in O(1) — that stored table is the memoization.
Worked Example: fib(6)
Set the 'Fibonacci index' slider to 6. Plain recursion makes 25 calls: fib(3) runs 3 times and fib(2) runs 5 times, as the tree shows. The table fills just 7 cells, [0] through [6], and the last one reads 8. At the final cell the readouts show Naive calls 25, DP calls 7 and a Speedup of 3.6×.
Watch the Gap Grow
Slide the 'Fibonacci index' up to 15. The naive count jumps to 1973 calls while the table needs only 16 cells, a 123.3× speedup. Naive calls grow by about 1.6× for each step of n — exponential growth — while the table grows by one cell. The recursion tree stays capped at fib(6) so it remains readable.
Read the Answer
When the header reads "Table complete!" the answer is simply looked up: fib(n) sits in cell [n]. Bottom-up tabulation takes O(n) time and O(n) space, and because each cell needs only the two before it, keeping just two running variables cuts the space to O(1).
How It Works — Step by Step
-
1
Spot the Repeated Work
Click 'Recursion tree' to see what plain recursion does. Every circle is one call, and each fib(k) calls fib(k−1) and fib(k−2). The orange circles are fib(3): it is computed three separate times inside fib(6), and the red circles mark the other repeats. That duplicated effort is the overlapping-subproblem signal dynamic programming exploits.
-
2
Start from the Base Cases
Click 'Table' to switch back. Cells [0] and [1] hold the base cases fib(0) = 0 and fib(1) = 1, so nothing needs computing. Press 'Next cell' to fill exactly one more cell and pause, so you can check each value before moving on. The yellow cell is the one being filled.
-
3
Each Cell Reuses Two Neighbours
Watch the blue arrows: every new cell adds the two cells to its left, and the formula line under the bars spells out the sum, such as fib(4) = fib(3) + fib(2) = 2 + 1 = 3. Each value is computed once, stored, then looked up in O(1) — that stored table is the memoization.
-
4
Worked Example: fib(6)
Set the 'Fibonacci index' slider to 6. Plain recursion makes 25 calls: fib(3) runs 3 times and fib(2) runs 5 times, as the tree shows. The table fills just 7 cells, [0] through [6], and the last one reads 8. At the final cell the readouts show Naive calls 25, DP calls 7 and a Speedup of 3.6×.
-
5
Watch the Gap Grow
Slide the 'Fibonacci index' up to 15. The naive count jumps to 1973 calls while the table needs only 16 cells, a 123.3× speedup. Naive calls grow by about 1.6× for each step of n — exponential growth — while the table grows by one cell. The recursion tree stays capped at fib(6) so it remains readable.
-
6
Read the Answer
When the header reads "Table complete!" the answer is simply looked up: fib(n) sits in cell [n]. Bottom-up tabulation takes O(n) time and O(n) space, and because each cell needs only the two before it, keeping just two running variables cuts the space to O(1).
Key Takeaways
Memoization eliminates redundant computation
Naive Fibonacci is O(2ⁿ) because it recomputes every subproblem exponentially many times. With memoization, each subproblem is solved exactly once — O(n) time.
Two approaches: top-down and bottom-up
Top-down memoization adds a cache to recursion. Bottom-up tabulation iterates over subproblems in dependency order. Both achieve the same complexity; bottom-up avoids call-stack overhead.
DP requires optimal substructure
DP works when the optimal solution to the whole problem contains optimal solutions to its subproblems. This property, combined with overlapping subproblems, is the hallmark of DP problems.
Connected Concepts
Recursion
Naive recursive solutions recompute the same subproblems — DP memoizes them for massive speedup.
Graph Traversal
Many DP problems reduce to shortest-path on a DAG, directly linked to graph traversal techniques.
Binary Search
Some DP optimisations use binary search to speed up transitions from O(n²) to O(n log n).
Big O Notation
The jump from 1973 naive calls to 16 table cells for fib(15) is exactly the gap between O(2ⁿ) and O(n) growth.
Fibonacci Sequence
The numbers filling the table are the Fibonacci sequence itself — each term the sum of the two before it.
Updated
- — Fill the table one cell at a time and compare the top-down recursion tree that repeats fib(3)