DP Patterns

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   Five families: state machine (modes per day), two-string prefixes, knapsack in disguise, sort + binary search, game ranges. Name the family; the state follows.

   #1
2. ↯use it when

   "cooldown / fee / at most k", "pattern with * must match all", "+ or − to hit target", "jobs with profit, no overlap", "both play optimally".

   #2
3. { }template

   Machine: save yesterday, then hold = max(hold, rest − p), sold = hold + p, rest = max(rest, sold). One line per arrow.

   #3
4. { }template

   Two strings: dp[i][j] over prefixes. Regex '*': dp[i][j−2] || (fits && dp[i−1][j]). Interleave: from s1 (↑) or from s2 (←).

   #4
5. O( )cost

   Stocks O(n) or O(n·k), memory O(1)/O(k). Two strings O(m·n). Target sum O(n·P). Jobs O(n log n). Game O(n²). Palindromes O(n²), O(1) memory.

   #5
6. !trap

   Never read a state you already changed today: save prev values first. Holding starts at −∞ (MIN_VALUE / 2), never 0.

   #6
7. !trap

   Weighted jobs: earliest-end greedy fails. Sort by end and binary-search jobs with end ≤ start (<=, not <).

   #7
8. ✦pro tip

   Target Sum: P = (total + target) / 2. Check parity and |target| ≤ total, then count subsets with a downward loop.

   #8
9. ✦pro tip

   Game DP: store my lead, not two scores: max(a[i] − lead[i+1][j], a[j] − lead[i][j−1]). Player 1 wins if it's ≥ 0.

   #9

Shaky on a card? Open the chapter or flip its recall cards.