Dynamic programming tables
Dynamic programming is taught as a recurrence and understood as a table, and the gap between those two is where most people give up. Three things close it and all three are visual: which cells the current cell depends on, drawn as arrows; the order the table fills, and why the dependencies force it; and the traceback, since the table holds the cost but the answer is the path back through it. Most explanations stop at the number, which is the half that is easy.
8 algorithms
- Fibonacci, bottom-upF(i) = F(i−1) + F(i−2)Fills a row of cells from left to right, each one the sum of the two before it, so nothing is ever computed twice — the smallest honest example of a table standing in for a recursion.O(n)O(n) space
- Fibonacci, top-down memoisedF(i) = memo[i] ?? F(i−1) + F(i−2)The same table as the bottom-up page, filled by a recursion that asks for a cell and either finds it already there or works it out and keeps it — so the order is right to left and the work is the same.O(n)O(n) space
- Coin changeC(a) = 1 + min over coins c of C(a − c)Works out the fewest coins that make every amount up to the target, trying each denomination at every amount — a one-dimensional table whose recurrence contains a real choice, and a traceback that says which coins were used.O(a · k)O(a) space
- 0/1 knapsackK(i, w) = max( K(i−1, w), value(i) + K(i−1, w − weight(i)) )Decides for each item whether taking it beats leaving it, at every capacity, filling a table one row per item — and the traceback says which items were chosen rather than only what they were worth.O(n · W)O(n · W) space
- Longest common subsequenceL(i, j) = a[i] = b[j] ? 1 + L(i−1, j−1) : max( L(i−1, j), L(i, j−1) )Compares two strings character by character across a table, taking a diagonal step when they match and the better of two neighbours when they do not — and the traceback reconstructs the subsequence itself.O(m · n)O(m · n) space
- Edit distanceD(i, j) = a[i] = b[j] ? D(i−1, j−1) : 1 + min( D(i−1, j), D(i, j−1), D(i−1, j−1) )Counts the fewest insertions, deletions and substitutions that turn one string into another, from three predecessors instead of two — and the traceback reads back as the list of edits itself.O(m · n)O(m · n) space
- Longest increasing subsequenceL(j) = 1 + max over i < j with a[i] < a[j] of L(i)Works out the longest increasing run ending at each position by looking back over every earlier position — a fill pattern where a cell has as many predecessors as there are cells before it.O(n²)O(n) space
- Matrix chain multiplicationM(i, j) = min over k in [i, j) of M(i, k) + M(k+1, j) + pᵢ₋₁ · pₖ · pⱼFinds the cheapest order in which to multiply a chain of matrices by solving every short subchain before any long one — which forces the table to fill along its diagonals rather than row by row.O(n³)O(n²) space
Nothing matches that. Clear the filter to see all 8.
The same Fibonacci computation is drawn as a call tree in Recursion. Sorting and searching live in AlgoLab, traversal and shortest paths inGraph algorithms, and pattern matching in String matching.