DP Pattern Map

One-page visual taxonomy of dynamic programming patterns — find the right approach in seconds. Pair with 04-dynamic-programming/ for full lessons and the DP vs Greedy Guide for the bigger decision.

---

Visual Taxonomy

DP Patterns
│
├── By Dimension
│   ├── 1D ────── dp[i]                 O(n) - O(n²)     linear sequences
│   ├── 2D ────── dp[i][j]              O(n²) - O(n³)    intervals, 2-param
│   ├── Bitmask ─ dp[mask]              O(2ⁿ * n)        subset enumeration
│   └── Interval  dp[l][r]              O(n²) - O(n³)    range merge/split
│
├── By Structure
│   ├── Linear ── sequence left to right                  LIS, knapsack
│   ├── Tree ──── dp on children, merge at parent         subtree problems
│   ├── DAG ───── topological order                       shortest path in DAG
│   └── Grid ──── dp[i][j] from neighbors                pathfinding, edit dist
│
├── By Optimization
│   ├── None ──────── brute transitions                   baseline
│   ├── Prefix sums ─ precompute range costs              O(1) cost lookup
│   ├── CHT ──────── Convex Hull Trick                    Li Chao / deque
│   ├── D&C opt ──── Divide & Conquer optimization        O(n k log n)
│   ├── Knuth opt ── monotone optimal split points         O(n³) -> O(n²) on interval DP
│   └── Aliens ──── Lambda / WQS binary search             remove one dimension
│
└── By Trick
    ├── Digit DP ──── dp by digit, tight flag              counting in [L,R]
    ├── SOS DP ────── Sum over Subsets                     O(2ⁿ * n)
    ├── Broken Profile  dp on grid column by column        plug DP
    ├── Slope Trick ── maintain piecewise-linear fn        abs-value DPs
    └── DP on Tree ── rerooting / subtree merge            tree-centered

---

Pattern Quick Reference

Note on the taxonomy: "dimension" (how many indices in the state) and "optimization" (how transitions are sped up) are independent axes. Knapsack is conceptually 2D over (item, capacity) but is usually compressed to 1D in implementation. LIS as dp[i] is O(n²); the O(n log n) form is patience sorting / BIT and is no longer ordinary DP — it is included here as a recognition pattern, not as the canonical DP form.

Pattern             Key idea                          Complexity     See file
──────────────────────────────────────────────────────────────────────────────
1D linear           dp[i] = best from dp[0..i-1]      O(n)-O(n²)     04-dp/02-dp-intro-1d.md
Knapsack            dp[i][w]; usually 1D-compressed   O(n*W)         04-dp/03-dp-knapsack.md
LIS (DP)            dp[i] = LIS ending at i           O(n²)          04-dp/04-dp-2d-sequence.md
LIS (patience)      binary search / BIT, not DP       O(n log n)     04-dp/04-dp-2d-sequence.md
2D sequence (LCS)   dp[i][j] over two strings         O(n*m)         04-dp/04-dp-2d-sequence.md
Interval DP         dp[l][r] = merge children         O(n³)          04-dp/05-dp-interval.md
Bitmask DP          dp[mask] subset states            O(2ⁿ*n)        04-dp/06-dp-bitmask.md
Digit DP            build number digit by digit       O(d*10*2)      04-dp/07-dp-digit.md
Tree DP             dp[v] from dp[children]           O(n)           04-dp/08-dp-on-trees.md
SOS DP              sum over subsets via bits         O(2ⁿ*n)        04-dp/09-dp-sos.md
CHT optimization    add lines, query min/max          O(n log n)     04-dp/10-dp-convex-hull-trick.md
D&C optimization    opt[i][j] monotone in j           O(nk log n)    04-dp/11-dp-divide-and-conquer-optimization.md
Slope trick         convex fn breakpoints             O(n log n)     04-dp/12-dp-slope-trick.md
Knuth optimization  quadrangle inequality             O(n³)->O(n²)   04-dp/13-dp-knuth-optimization.md
Aliens trick        lambda / WQS binary search        depends        04-dp/14-aliens-trick.md

04-dp/ here resolves to ../04-dynamic-programming/ — only the path is shortened for the poster.

---

"Which DP Do I Need?" Flowchart

Start
  │
  ├── Counting numbers with digit constraints?
  │   └─-> Digit DP
  │
  ├── Subset/bitmask with n <= 20?
  │   ├── Need sum over all subsets? -> SOS DP
  │   └── Otherwise -> Bitmask DP
  │
  ├── Problem on a tree?
  │   ├── Need answer for every root? -> Rerooting DP
  │   └── Single root? -> Tree DP
  │
  ├── Merging intervals / parenthesization?
  │   └─-> Interval DP  dp[l][r]
  │
  ├── Grid pathfinding / edit distance?
  │   └─-> Grid DP  dp[i][j]
  │
  ├── Linear recurrence with large n?
  │   └─-> Matrix Exponentiation  (see ../07-mathematics/09-matrix-exponentiation.md)
  │
  ├── 1D DP too slow?
  │   ├── Transitions look like y = mx + b? -> CHT
  │   ├── Optimal split point monotone?     -> D&C opt / Knuth opt
  │   └── Can trade a dimension for λ?      -> Aliens trick (WQS)
  │
  └── None of the above
      └─-> Standard 1D/2D DP -- define states & transitions

---

See also: 07-dp-vs-greedy-guide.md for DP vs Greedy decision making.