Dynamic Programming Mind Map
Algorithm & Systems VisualizationsEvery dynamic programming visualization on this site on one map. The branches are the main ideas. Each leaf is a page; the grey line under it is the one thing to remember about it. Click a branch to focus on it, click a page to open it.
1. How the map is organized
Ask what one table cell stands for, and you know the branch:
- A prefix of one sequence? One-row DP. A prefix of items plus a capacity or sum: knapsack family.
- Prefixes of two strings? Two strings. A cell of a picture-like grid: grid DP.
- A range i..j that you split? Interval DP, filled by length. Anything stranger (eggs and floors, a subset of cities): unusual states.
- Pages about how to run any DP (memo or table) sit on recursion to table.
2. The branches side by side
| Branch | State | Fill order | Typical time |
|---|---|---|---|
| Recursion to table | a recursive call's arguments | top-down memo or bottom-up | states × work per state |
| One-row DP | dp[i] | left to right | O(n) to O(n²) |
| Knapsack family | dp[i][w] items × capacity | row by row | O(n·W), pseudo-polynomial |
| Two strings | dp[i][j] prefixes | row by row | O(m·n) |
| Grid DP | dp[r][c] cell | top-left to bottom-right | O(m·n) |
| Interval DP | dp[i][j] range | by range length | O(n³) |
| Unusual states | eggs × floors, subset × city | by subset or count | Held-Karp O(n²·2ⁿ) |
3. Five facts to remember
- DP needs two things: overlapping subproblems and optimal substructure.
- Running time = number of states × work to compute one state.
- Memoization (top-down) and tabulation (bottom-up) compute the same values in different orders.
- Keep a choice table or trace back from the last cell to recover the actual answer, not just its value.
- Knapsack's O(n·W) is pseudo-polynomial: it grows with the value of W, not its number of digits.
See all dynamic programming pages in the index, or the other mind maps.