Dynamic Programming

Solve complex problems by breaking them into overlapping subproblems

Computer Science Algorithms advanced 15 min

This concept builds on Recursion — Functions That Call Themselves, Graph Traversal. Consider exploring them first for the best experience.

Step 1 of 6

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

Step 1 of 6
  1. 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. 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. 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. 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. 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. 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.

Added
Updated
  • — Fill the table one cell at a time and compare the top-down recursion tree that repeats fib(3)