Dynamic programming, memoisation and tabulation
Dynamic programming applies when a problem has optimal substructure — the best answer is built from best answers to subproblems — and overlapping subproblems, meaning the same subproblem recurs many times. Caching those repeats collapses exponential recursion to polynomial time.
Top-down memoisation adds a cache to the natural recursion; bottom-up tabulation fills a table in dependency order and avoids the call stack entirely. The visualizer shows the table filling cell by cell, with each cell's dependencies highlighted.
Time and space complexity
| Problem | Time | Space | Space-optimised |
|---|---|---|---|
| Fibonacci | O(n) | O(n) | O(1) with two variables |
| Climbing stairs | O(n) | O(n) | O(1) |
| 0/1 Knapsack | O(n × W) | O(n × W) | O(W) with a rolling row |
| Longest common subsequence | O(n × m) | O(n × m) | O(min(n, m)) |
| Coin change | O(n × amount) | O(amount) | O(amount) |
How to use this visualizer
Choose a DP problem to load its recurrence and table.
Step through and watch each cell computed from its dependencies.
Follow the highlighted dependency arrows to see the recurrence applied.
Trace back from the final cell to reconstruct the chosen solution.
Frequently asked questions
Memoisation is top-down: you write the natural recursion and cache each result so repeated subproblems return instantly. Tabulation is bottom-up: you iterate subproblems in dependency order and fill a table, no recursion involved. Memoisation only computes the subproblems actually reached; tabulation avoids stack-depth limits and is usually easier to space-optimise.
Look for two signals together. Optimal substructure: the answer decomposes into answers of smaller instances. Overlapping subproblems: a plain recursion would recompute the same inputs repeatedly. Problems asking for a count of ways, a minimum or maximum over choices, or whether a target is reachable are usually DP. If subproblems never repeat, divide and conquer is the better fit.
Check which previous rows or columns the recurrence actually reads. If each cell depends only on the row above, keep two rows and swap them, or iterate a single row backwards — that turns O(n × W) into O(W). Knapsack, LCS, and edit distance all admit this optimisation, at the cost of losing the full table needed to reconstruct the solution path.