DP Patterns

Hard DP questions come in a few families. Name the family, and the state, the table and the loop order follow.

advanced~160 min6 simulations11 problems

▶ guided lesson ⚡ 1-minute summary ↻ 14 recall cards

before this: Dynamic Programming · Arrays & Strings · Binary Search · Intervals

Section

01 · why it exists

Why this exists, and the weight it carries

since1952–67

State-machine DP

Richard Bellman (stages and states); Andrew Viterbi (best path per state per time step)

Bellman's dynamic programming (see the Dynamic Programming chapter) already thinks in stages and states: at each stage you are in some state, and the best future depends only on that state. In 1967 Andrew Viterbi published a decoding algorithm for convolutional codes that keeps, for every state of the encoder at every time step, the best path that ends there — one best number per state per step, the same table the stock problems fill. The stock-trading series itself (I–IV, cooldown, fee) is interview folklore with no inventor.

the problem it solvedChoosing the best sequence of actions when what you may do next depends on the mode you are in — holding or not, cooling down, trades used — without listing every sequence.

its jobs today

Backtesting trading rules (illustrative): a simulator replays prices day by day while the strategy is always in one mode — out of the market, holding, or waiting after an exit.
Radios: GSM calls, 4G LTE's control channels and Wi-Fi's basic coding mode use convolutional codes, usually decoded with the Viterbi algorithm — the best score per state per time step. (5G uses LDPC and polar codes instead.)
Speech and handwriting recognition: in HMM-based recognisers the same per-state, per-step table picks the most likely hidden sequence.

the weight it carries

Illustrative: 10 years of daily prices at about 252 trading days a year (a common rule of thumb) = 2,520 days, at most 5 trades. Acting or waiting each day gives up to 2²⁵²⁰ plans. The machine has 2 × 5 = 10 states: 2,520 × 10 = 25,200 updates.

without it

Every "what I may do next depends on what I did before" question would mean trying every action sequence — exponential in the number of days.

when · why · how

when: Each step you are in one of a few modes, and the legal moves depend on the mode: holding or not, cooling down, k trades used.
why: Time = steps × states × moves: O(n) for cooldown or fee, O(n·k) for k trades. Memory is O(states), because a day reads only the day before.
how: One int per state (hold, sold, rest) or arrays buy[t], sell[t]; save yesterday's values before overwriting; Integer.MIN_VALUE / 2 for impossible states.

since1951–68

Regular-expression matching

Stephen Kleene; Ken Thompson

In a December 1951 RAND memo (later printed in Automata Studies, 1956), Stephen Kleene asked which "events" a nerve net or finite automaton can respond to, and described them with an algebra of regular events: union, concatenation and an iterate operation (written EF) that became today's Kleene star. Ken Thompson turned the idea into a tool. His QED editor for MIT's CTSS compiled each regular expression into machine code that simulated a nondeterministic finite automaton, and he published the method in Communications of the ACM* in June 1968. In 2007 Russ Cox showed why it still matters: backtracking matchers (Perl in his tests; Java's also backtracks) can take exponential time on patterns that a Thompson-style simulation finishes in microseconds.

the problem it solvedDescribing a whole family of strings with a short pattern, and deciding quickly — without trying every split — whether a string belongs to it.

its jobs today

Search: grep, IDE find-and-replace and log filters match lines against regular expressions.
Validation: s.matches("[6-9][0-9]{9}") checks a 10-digit Indian mobile number in one line.
Routing: web servers and API gateways pick a handler by matching the URL path against patterns.

the weight it carries

Illustrative: text = 20 a's, pattern = a*a*a*a*a*a*a*a*b (8 stars, then a b that never comes). Plain recursion tries every way to hand out up to 20 a's to the 8 stars: C(28, 8) = 3,108,105 dead ends. The table has 21 × 18 = 378 cells, O(1) each.

without it

A matcher that backtracks blindly can take exponential time on a short input; a table or an automaton keeps it at O(text × pattern) or better.

when · why · how

when: Pattern matching with '.'/'?' and '*', where the whole string must match.
why: (m + 1)(n + 1) states × O(1) = O(m·n), instead of exponential backtracking.
how: boolean[][] dp = new boolean[m + 1][n + 1], dp[0][0] = true; for a '*': dp[i][j] = dp[i][j - 2] || (fits && dp[i - 1][j]).

since1975

Palindromic substrings: centres, tables and Manacher

Glenn Manacher

Growing palindromes from their centres is folklore; the famous speed-up has a name. In 1975 Glenn Manacher published, in the Journal of the ACM, a linear-time "on-line" algorithm for finding the smallest palindrome at the start of a string. Its trick — reuse what a known palindrome already says about its mirror half — is the heart of what interviewers call Manacher's algorithm: the radius at every centre in O(n). Interviews almost always accept the O(n²) expansion.

the problem it solvedFinding palindromes without re-checking the same letters again and again: O(n) instead of O(n²) or O(n³).

its jobs today

A building block for string DP: Palindrome Partitioning and Longest Palindromic Subsequence start from the same pal[i][j] table.
Bioinformatics: DNA "palindromes" such as EcoRI's recognition site GAATTC read the same on both strands (complement CTTAAG, read backwards GAATTC); centre expansion with a complement check finds them.

the weight it carries

Illustrative: 1,000 identical letters, the worst case. Checking every substring with two pointers: 83,458,250 comparisons. Expanding from 2n − 1 = 1,999 centres: at most n(n + 1)/2 + 1,999 = 502,499. Manacher: O(n), a few thousand steps.

without it

Palindrome questions would cost O(n³): in the worst case (one repeated letter) a 10⁴-letter text would need about 8.3 × 10¹⁰ comparisons instead of about 5 × 10⁷.

when · why · how

when: Count or find palindromic substrings (contiguous blocks).
why: O(n²) time and O(1) memory by expanding; the pal[i][j] table costs O(n²) memory but can feed later DPs.
how: for c: count += expand(c, c) + expand(c, c + 1), where expand moves lo--, hi++ while the characters match and counts every step.

since?

Knapsack in disguise: signs to a subset sum

The sign-to-subset rewrite is two lines of algebra with no inventor. Knapsack's own history (Mathews, Bellman and Dreyfus, Dantzig, Karp) is told in the Dynamic Programming chapter.

its jobs today

Reconciling accounts: which of these credits and debits net out to exactly this balance? Giving each amount a sign is choosing a subset.
Splitting work between two machines or teams so their totals differ by a set amount — Last Stone Weight II is the same rewrite.

the weight it carries

Illustrative: 20 numbers adding up to 1,000, target 100. Trying every sign: 2²⁰ = 1,048,576 patterns × 20 additions ≈ 2.1 × 10⁷ steps. Subset count: P = (1,000 + 100) / 2 = 550, so at most 20 × 551 = 11,020 cell updates.

without it

Every ± assignment or "split into two groups" count would stay exponential: 40 numbers already have 2⁴⁰ ≈ 1.1 × 10¹² sign patterns.

when · why · how

when: You put + or − on items, or split them into two groups, and the question is about the difference between the groups.
why: The '+' group alone decides everything: P = (total + target) / 2. Then it's a 0/1 subset count — O(n·P) time, O(P) memory, pseudo-polynomial but fine while the total is small.
how: Check Math.abs(target) <= total and parity; int[] ways = new int[P + 1]; ways[0] = 1; then for each x loop s DOWN from P to x: ways[s] += ways[s - x].

since?

Weighted interval scheduling (sort + DP + binary search)

No documented first inventor. Kleinberg and Tardos's Algorithm Design (2005) opens its dynamic-programming chapter with it — sections 6.1 and 6.2 are both "Weighted Interval Scheduling". Its unweighted cousin, earliest end first, is the greedy algorithm in the Intervals chapter.

its jobs today

Renting one resource: a single GPU server, a studio or a hall takes paid bookings that can't overlap — accept the set worth the most.
Ad and broadcast slots: choose non-overlapping slots with the highest total value.

the weight it carries

Illustrative: 50,000 jobs (LeetCode's limit). Every subset: 2⁵⁰⁰⁰⁰ — impossible. DP scanning back for each job: up to n²/2 = 1.25 × 10⁹ steps. Sort + binary search: the sort and the searches each take about n × ⌈log₂ n⌉ = 50,000 × 16 = 8 × 10⁵ steps.

without it

Once jobs have values, greedy earliest-end is wrong (one long, rich job beats three short ones), so the only safe fallback would be trying subsets.

when · why · how

when: Intervals that each carry a value; pick non-overlapping ones for the largest total.
why: n states (jobs sorted by end), each needing one O(log n) search → O(n log n) with the sort, O(n) memory.
how: Arrays.sort(jobs, (a, b) -> Integer.compare(a[1], b[1])); best[i] = Math.max(best[i - 1], profit + best[k]) with k from a binary search — or a TreeMap<end, best> and floorEntry(start).

since1928

Game DP (minimax on what's left)

John von Neumann

In 1928 John von Neumann published "Zur Theorie der Gesellschaftsspiele" (usually translated "On the Theory of Games of Strategy") in Mathematische Annalen, proving the minimax theorem for two-player zero-sum games. The idea we use: assume the opponent always makes their best reply, and pick the move whose worst case is best. With perfect information you can compute that value backwards from the end of the game. In 2007 Jonathan Schaeffer's team announced in Science that checkers (English draughts) is solved — perfect play by both sides is a draw — after computers had worked on the proof almost continuously since 1989.

the problem it solvedDeciding the best move when an intelligent opponent moves in between — the value of a game under perfect play.

its jobs today

Game engines: chess and board-game programs search minimax trees and cache positions they have already scored — memoization under the name "transposition table".
Solved games and endgame tables: the perfect-play result of positions is computed backwards from the end of the game and stored.

the weight it carries

Illustrative: 20 numbers (LeetCode's limit). Plain minimax: 2²⁰ − 1 = 1,048,575 calls. Memo or table: n(n + 1)/2 = 210 ranges, two choices each.

without it

Every "both play optimally" question would need the whole game tree: 2ⁿ − 1 calls for n numbers — about 1.1 × 10¹² for 40.

when · why · how

when: Two players alternate, both play perfectly, and what's left is small to describe (a range i..j, a pile size, a position).
why: One number per state — the mover's best lead — and one minus sign switches perspective. O(states × moves): O(n²) here.
how: lead[i][j] = Math.max(nums[i] - lead[i + 1][j], nums[j] - lead[i][j - 1]), filled by range length; player 1 wins if lead[0][n - 1] >= 0.

02 · plain english

The idea in 30 seconds

Most "hard" DP questions are one of a few families in a new costume. Spot the family and the state almost writes itself.

Each family has a fixed state shape: modes per day (stocks), two prefixes (regex, interleaving), a sum (target sum), jobs sorted by end (scheduling), a range and whose turn it is (games).

The ladder from the previous chapter doesn't change: brute-force recursion → memo → table → squeeze the memory.

picture this

A Java thread is always in exactly one Thread.State (NEW, RUNNABLE, WAITING, TERMINATED, …), and only some moves between them are legal (a TERMINATED thread never runs again). State-machine DP is that picture with a number written on each state: every day you are in one mode (holding a share, just sold, free to buy), each legal move is an arrow, and dp keeps the best profit you could have in each mode. Draw the circles and arrows first; the code is one Math.max per arrow.

03 · remember

What you must know

Families, not problems. State machine (modes per step), two-string prefixes, knapsack in disguise, sort + binary search, and game ranges. Each has a state you can write down before any code.
State-machine DP: one variable per mode, one Math.max per arrow. Cooldown = HOLD, SOLD, REST. Fee = CASH, HOLD with the fee on the sell arrow. Save yesterday's values before overwriting them.
"At most k" goes into the state: buy[t], sell[t] for t = 1..k, so O(n·k) time and O(k) memory. If k ≥ n/2 the limit can't bind — just add every rise.
Impossible states start at −∞ (Integer.MIN_VALUE / 2 in Java), never at 0 — a 0 in HOLD would mean a free share.
Two strings, new transitions: regex * = zero copies (dp[i][j−2]) or one more copy (dp[i−1][j]); interleaving = the next letter came from s1 (↑) or s2 (←); distinct subsequences = skip this letter or use it (counting with +).
Palindromic substrings: 2n − 1 centres, count every successful expansion. O(n²) time, O(1) memory. The pal[i][j] table gives the same count with O(n²) memory; Manacher's O(n) is a follow-up only.
Knapsack in disguise: signs + and − split the numbers into two groups. P − N = target and P + N = total, so P = (total + target) / 2 — count subsets with that sum, loop downward.
Weighted interval scheduling: sort by end; best[i] = max(skip: best[i−1], take: profit + best[k]), where k = how many jobs end by this start — a binary search. O(n log n). Greedy works only when every job is worth the same.
Game DP: both play perfectly, so store one number per range — my best lead. lead[i][j] = max(a[i] − lead[i+1][j], a[j] − lead[i][j−1]). The minus sign is the opponent's best reply.
Cost is still states × work per state: stocks n·(states), strings m·n, target sum n·P, scheduling n·log n, games n².

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

State machine: buy, sell, cool down

Three boxes are the three modes; the green arrow is the move that won today. The table below keeps every day's numbers so you can trace the best plan back.

loading simulation…

javajava.util.*

1class Solution {2    public int maxProfit(int[] prices) {3        int hold = Integer.MIN_VALUE / 2; // best profit while holding a share: impossible before day 04        int sold = Integer.MIN_VALUE / 2; // best profit if we sold today5        int rest = 0;                     // best profit holding nothing, free to buy6        for (int p : prices) {7            int prevHold = hold, prevSold = sold, prevRest = rest; // yesterday's three numbers8            hold = Math.max(prevHold, prevRest - p); // keep holding, or buy (never right after a sale)9            sold = prevHold + p;                     // sell the share we were holding10            rest = Math.max(prevRest, prevSold);     // stay out, or yesterday's sale cools down11        }12        return Math.max(sold, rest); // ending while holding a share is never best13    }14}

sim

At most k trades: a chain of states

BUY 1 → SELL 1 → BUY 2 → SELL 2 …: each trade adds two states to the chain. Every day walks the chain once.

loading simulation…

javajava.util.*

1class Solution {2    public int maxProfit(int k, int[] prices) {3        int[] buy = new int[k + 1];  // buy[t]: best profit while holding the t-th share4        int[] sell = new int[k + 1]; // sell[t]: best profit after t completed sales (sell[0] = 0)5        Arrays.fill(buy, Integer.MIN_VALUE / 2); // nothing bought yet6        for (int p : prices) {7            for (int t = 1; t <= k; t++) {8                buy[t] = Math.max(buy[t], sell[t - 1] - p); // keep holding, or buy after t - 1 sales9                sell[t] = Math.max(sell[t], buy[t] + p);    // keep, or sell the t-th share today10            }11        }12        return sell[k]; // "at most k": sell[k] is never below sell[t] for t < k13    }14}

sim

Regex table: zero copies or one more

Rows use more of the text, columns more of the pattern. A '*' cell looks two columns left (zero copies) or one row up (eat one more letter).

loading simulation…

javajava.util.*

1class Solution {2    public boolean isMatch(String s, String p) {3        int m = s.length(), n = p.length();4        boolean[][] dp = new boolean[m + 1][n + 1]; // dp[i][j]: does s[0..i) match p[0..j)?5        dp[0][0] = true; // empty text, empty pattern6        for (int j = 2; j <= n; j++) {7            if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2]; // "a*b*" can match nothing8        }9        for (int i = 1; i <= m; i++) {10            for (int j = 1; j <= n; j++) {11                char pc = p.charAt(j - 1);12                if (pc == '*') {13                    dp[i][j] = dp[i][j - 2]; // zero copies of the starred char14                    if (same(s.charAt(i - 1), p.charAt(j - 2))) dp[i][j] |= dp[i - 1][j]; // one more copy15                } else {16                    dp[i][j] = same(s.charAt(i - 1), pc) && dp[i - 1][j - 1];17                }18            }19        }20        return dp[m][n];21    }22 23    private boolean same(char c, char pc) {24        return pc == '.' || pc == c;25    }26}

sim

Signs become a subset count

First the algebra picks the sum the '+' group needs; then one row of counts is swept downward, once per number.

loading simulation…

javajava.util.*

1class Solution {2    public int findTargetSumWays(int[] nums, int target) {3        int total = 0;4        for (int x : nums) total += x;5        // plus - minus = target and plus + minus = total, so plus = (total + target) / 26        if (Math.abs(target) > total || (total + target) % 2 != 0) return 0;7        int want = (total + target) / 2; // the '+' numbers must add up to exactly this8        int[] ways = new int[want + 1]; // ways[s]: subsets of the numbers seen so far with sum s9        ways[0] = 1; // the empty subset10        for (int x : nums) {11            for (int s = want; s >= x; s--) { // DOWNWARD: each number joins a subset at most once12                ways[s] += ways[s - x]; // subsets without x, plus subsets that add x13            }14        }15        return ways[want];16    }17}

sim

Jobs sorted by end + binary search

The timeline shows each job's span. For each job, binary search counts the jobs that finish in time (amber), then best[i] picks skip or take.

loading simulation…

javajava.util.*

1class Solution {2    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {3        int n = startTime.length;4        int[][] jobs = new int[n][];5        for (int i = 0; i < n; i++) jobs[i] = new int[] {startTime[i], endTime[i], profit[i]};6        Arrays.sort(jobs, (a, b) -> Integer.compare(a[1], b[1])); // by END time7        int[] best = new int[n + 1]; // best[i]: max profit using only the first i jobs (best[0] = 0)8        for (int i = 1; i <= n; i++) {9            int[] job = jobs[i - 1];10            int k = countEndingBy(jobs, i - 1, job[0]); // jobs 0..k-1 all end by this start11            best[i] = Math.max(best[i - 1], job[2] + best[k]); // skip it, or take it after those k12        }13        return best[n];14    }15 16    /** How many of jobs[0..hi) end at or before `time`? They are sorted by end, so binary search. */17    private int countEndingBy(int[][] jobs, int hi, int time) {18        int lo = 0;19        while (lo < hi) {20            int mid = (lo + hi) >>> 1;21            if (jobs[mid][1] <= time) lo = mid + 1; // mid fits: the answer is to its right22            else hi = mid; // mid ends too late23        }24        return lo;25    }26}

sim

Game DP: one lead per range

Each cell is the best lead the player to move can force on that range. Short ranges first; the last frame replays one perfect game.

loading simulation…

javajava.util.*

1class Solution {2    public boolean predictTheWinner(int[] nums) {3        int n = nums.length;4        int[][] lead = new int[n][n]; // lead[i][j]: best (mover - other) on nums[i..j]5        for (int i = 0; i < n; i++) lead[i][i] = nums[i]; // one number left: the mover takes it6        for (int len = 2; len <= n; len++) { // short ranges first: they are what longer ones read7            for (int i = 0; i + len - 1 < n; i++) {8                int j = i + len - 1;9                int takeLeft = nums[i] - lead[i + 1][j];  // I take nums[i]; the opponent then leads on i+1..j10                int takeRight = nums[j] - lead[i][j - 1]; // I take nums[j]; the opponent then leads on i..j-111                lead[i][j] = Math.max(takeLeft, takeRight);12            }13        }14        return lead[0][n - 1] >= 0; // a tie still counts as a win for player 115    }16}

05 · cost

Time & space, explained

State-machine DP over n days
	Time	Extra space	why
Brute force: try every action	O(2ⁿ)	O(n)	Act or wait on every day, nothing remembered; the space is the recursion depth.
Cooldown (3 states) / fee (2 states)	O(n)	O(1)	n days × a constant number of states; each day reads only yesterday's numbers.
At most 2 trades (4 states)	O(n)	O(1)	buy1, sell1, buy2, sell2: four max() lines per day.
At most k trades (2k states)	O(n·k)	O(k)	Every day walks t = 1..k with two updates each. If k ≥ n/2, adding every rise is O(n).

The other families
	Time	Table space	Optimised space	why
Regex matching (text m, pattern n)	O(m·n)	O(m·n)	O(n)	(m + 1)(n + 1) cells, O(1) each; a row reads itself and the row above, so two rows would do.
Interleaving String	O(m·n)	O(m·n)	O(n)	One cell per (i, j) prefix pair; each reads up and left, so one row is enough.
Distinct Subsequences	O(m·n)	O(m·n)	O(n)	Each cell reads up and up-left: one row, filled right to left like 0/1 knapsack.
Palindromic Substrings	O(n²)	O(n²)	O(1)	2n − 1 centres × up to n/2 steps; the pal[i][j] table needs n² booleans, expanding needs none.
Target Sum (P = (total + target) / 2)	O(n·P)	O(n·P)	O(P)	n numbers × P sums; pseudo-polynomial, fine because the total is at most 1,000.
Max Profit in Job Scheduling	O(n log n)	O(n)	O(n)	The sort, then one O(log n) binary search per job.
Predict the Winner (game on a range)	O(n²)	O(n²)	O(n)	n(n + 1)/2 ranges × 2 choices; one row is enough if i runs downward.

06 · java

Raw vs Collections Framework

State machine: a table per day, or a few rolling variables

javaint[][] dp: one row per day, one column per statejava.util.*

1class Table {2    public int maxProfit(int[] prices) {3        int n = prices.length;4        final int HOLD = 0, SOLD = 1, REST = 2;5        int[][] dp = new int[n + 1][3]; // dp[d][state]: best profit after the first d days, ending in that state6        dp[0][HOLD] = Integer.MIN_VALUE / 2; // can't hold a share before day 0 (half of MIN so "+ price" can't overflow)7        dp[0][SOLD] = Integer.MIN_VALUE / 2; // can't have sold one either8        dp[0][REST] = 0;9        for (int d = 1; d <= n; d++) {10            int p = prices[d - 1];11            dp[d][HOLD] = Math.max(dp[d - 1][HOLD], dp[d - 1][REST] - p); // keep holding, or buy (only from REST)12            dp[d][SOLD] = dp[d - 1][HOLD] + p;                             // sell the share we held13            dp[d][REST] = Math.max(dp[d - 1][REST], dp[d - 1][SOLD]);      // stay out, or cool down after a sale14        }15        return Math.max(dp[n][SOLD], dp[n][REST]);16    }17}

javathree rolling intsjava.util.*

1class Solution {2    public int maxProfit(int[] prices) {3        int hold = Integer.MIN_VALUE / 2; // best profit while holding a share: impossible before day 04        int sold = Integer.MIN_VALUE / 2; // best profit if we sold today5        int rest = 0;                     // best profit holding nothing, free to buy6        for (int p : prices) {7            int prevHold = hold, prevSold = sold, prevRest = rest; // yesterday's three numbers8            hold = Math.max(prevHold, prevRest - p); // keep holding, or buy (never right after a sale)9            sold = prevHold + p;                     // sell the share we were holding10            rest = Math.max(prevRest, prevSold);     // stay out, or yesterday's sale cools down11        }12        return Math.max(sold, rest); // ending while holding a share is never best13    }14}

Name the states (HOLD, SOLD, REST constants or variables). Bare 0/1/2 indexes are where state-machine bugs hide.
Integer.MIN_VALUE / 2 means "impossible". Half of MIN leaves room: with plain MIN_VALUE, hold + p - fee wraps around to a huge positive number whenever p < fee.
Save yesterday's values (prevHold, prevSold, prevRest) before writing today's, or every update reads a value you already changed.

Negative sums as states: shift into an array, or key a HashMap

javaint[][] memo, index = sum + totaljava.util.*

1class Solution {2    public int findTargetSumWays(int[] nums, int target) {3        int total = 0;4        for (int x : nums) total += x;5        // The running sum lives in [-total, total]: shift it by +total to get an array index.6        int[][] memo = new int[nums.length][2 * total + 1];7        for (int[] row : memo) Arrays.fill(row, -1); // -1 = unknown (counts are never negative)8        return ways(nums, 0, 0, target, total, memo);9    }10 11    private int ways(int[] nums, int i, int sum, int target, int total, int[][] memo) {12        if (i == nums.length) return sum == target ? 1 : 0;13        if (memo[i][sum + total] != -1) return memo[i][sum + total];14        int count = ways(nums, i + 1, sum + nums[i], target, total, memo)15                  + ways(nums, i + 1, sum - nums[i], target, total, memo);16        return memo[i][sum + total] = count;17    }18}

javaHashMap<Long, Integer>, two ints packed in one keyjava.util.*

1/** Target Sum, memoized with a HashMap: the key packs (index, running sum), negative sums included. */2static int waysWithMap(int[] nums, int target) {3    return ways(nums, 0, 0, target, new HashMap<>());4}5 6static int ways(int[] nums, int i, int sum, int target, Map<Long, Integer> memo) {7    if (i == nums.length) return sum == target ? 1 : 0;8    long key = ((long) i << 32) | (sum & 0xFFFFFFFFL); // two ints in one long: no String building9    Integer cached = memo.get(key);10    if (cached != null) return cached;11    int count = ways(nums, i + 1, sum + nums[i], target, memo) + ways(nums, i + 1, sum - nums[i], target, memo);12    memo.put(key, count);13    return count;14}

A running sum in [−total, total] becomes an index with sum + total; the array needs 2 * total + 1 slots.
A HashMap takes any key but boxes every int and hashes on every lookup — noticeably slower than an array index.
Pack two ints into one long key ((long) i << 32 | (sum & 0xFFFFFFFFL)) instead of building an i + "," + sum String on every call.
Even better: Target Sum's algebra removes negative states entirely — that's the optimal approach.

Last job that fits: a hand-written binary search, or TreeMap.floorEntry

javasorted int[][] + binary searchjava.util.*

1class Solution {2    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {3        int n = startTime.length;4        int[][] jobs = new int[n][];5        for (int i = 0; i < n; i++) jobs[i] = new int[] {startTime[i], endTime[i], profit[i]};6        Arrays.sort(jobs, (a, b) -> Integer.compare(a[1], b[1])); // by END time7        int[] best = new int[n + 1]; // best[i]: max profit using only the first i jobs (best[0] = 0)8        for (int i = 1; i <= n; i++) {9            int[] job = jobs[i - 1];10            int k = countEndingBy(jobs, i - 1, job[0]); // jobs 0..k-1 all end by this start11            best[i] = Math.max(best[i - 1], job[2] + best[k]); // skip it, or take it after those k12        }13        return best[n];14    }15 16    /** How many of jobs[0..hi) end at or before `time`? They are sorted by end, so binary search. */17    private int countEndingBy(int[][] jobs, int hi, int time) {18        int lo = 0;19        while (lo < hi) {20            int mid = (lo + hi) >>> 1;21            if (jobs[mid][1] <= time) lo = mid + 1; // mid fits: the answer is to its right22            else hi = mid; // mid ends too late23        }24        return lo;25    }26}

javaTreeMap<end time, best profit>java.util.*

1class Solution {2    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {3        int n = startTime.length;4        int[][] jobs = new int[n][];5        for (int i = 0; i < n; i++) jobs[i] = new int[] {startTime[i], endTime[i], profit[i]};6        Arrays.sort(jobs, (a, b) -> Integer.compare(a[1], b[1])); // by end time7        TreeMap<Integer, Integer> best = new TreeMap<>(); // end time -> best profit finished by then8        best.put(0, 0);9        for (int[] job : jobs) {10            int take = job[2] + best.floorEntry(job[0]).getValue(); // best plan that ends by this start11            if (take > best.lastEntry().getValue()) best.put(job[1], take); // keep values increasing12        }13        return best.lastEntry().getValue();14    }15}

Keep each job's start, end and profit together (int[][] jobs) before sorting — sorting the three arrays separately scrambles the jobs.
Integer.compare(a[1], b[1]) is the safe comparator habit; a[1] - b[1] breaks when values can be far apart in sign.
floorEntry(start) returns the entry with the greatest key ≤ start in O(log n): "the best plan that has finished by now".
Only put a strictly better total, so map values grow with the key and the floor entry is also the best one.

Game DP: count your total, or count your lead

javathe most the mover can collect (needs prefix sums)java.util.*

1/** Game DP, the other way round: the most the player to move can COLLECT from nums[i..j]. */2static boolean firstPlayerWins(int[] nums) {3    int n = nums.length;4    int[] prefix = new int[n + 1];5    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];6    int[][] collect = new int[n][n];7    for (int i = 0; i < n; i++) collect[i][i] = nums[i];8    for (int len = 2; len <= n; len++) {9        for (int i = 0; i + len - 1 < n; i++) {10            int j = i + len - 1;11            int rangeSum = prefix[j + 1] - prefix[i];12            // Whatever I leave behind, the opponent collects their best of it; I get the rest of the range.13            collect[i][j] = rangeSum - Math.min(collect[i + 1][j], collect[i][j - 1]);14        }15    }16    int mine = collect[0][n - 1];17    return mine >= prefix[n] - mine; // my total vs. what's left for the opponent18}

javaone lead table (mover − other)java.util.*

1class Solution {2    public boolean predictTheWinner(int[] nums) {3        int n = nums.length;4        int[][] lead = new int[n][n]; // lead[i][j]: best (mover - other) on nums[i..j]5        for (int i = 0; i < n; i++) lead[i][i] = nums[i]; // one number left: the mover takes it6        for (int len = 2; len <= n; len++) { // short ranges first: they are what longer ones read7            for (int i = 0; i + len - 1 < n; i++) {8                int j = i + len - 1;9                int takeLeft = nums[i] - lead[i + 1][j];  // I take nums[i]; the opponent then leads on i+1..j10                int takeRight = nums[j] - lead[i][j - 1]; // I take nums[j]; the opponent then leads on i..j-111                lead[i][j] = Math.max(takeLeft, takeRight);12            }13        }14        return lead[0][n - 1] >= 0; // a tie still counts as a win for player 115    }16}

Total form: collect = rangeSum − min(opponent's best on what you leave). Needs prefix sums; answers "how many points" directly.
Lead form: lead = take − lead(rest). One table, no sums, and the sign of lead[0][n − 1] is the winner.

Java API you will actually use
call	does	cost
`Integer.MIN_VALUE / 2`	−∞ for impossible states (holding before any buy); leaves room for ± a price without wrapping	O(1)
`Math.max(keep, move)`	Every state update: stay where you are, or arrive along an arrow	O(1)
`Arrays.fill(buy, Integer.MIN_VALUE / 2)`	Start every "holding share t" state as impossible	O(k)
`new boolean[m + 1][n + 1]`	Two-string table; row 0 / column 0 = the empty prefix	O(m·n)
`s.charAt(i - 1)`	The last letter of the prefix of length i (the table is shifted by one)	O(1)
`Arrays.sort(jobs, (a, b) -> Integer.compare(a[1], b[1]))`	Sort int[][] rows by their end time	O(n log n)
`map.floorEntry(key) / map.lastEntry()`	TreeMap: greatest key ≤ key (or null) / the largest key	O(log n)
`new Integer[n][n] / new Boolean[m + 1][n + 1]`	Memo where null = unknown (leads can be 0 or negative; matches can be false)	O(n²) / O(m·n)
`"a".repeat(n)`	Build long test strings quickly (Java 11+)	O(n)

A few modes per step (holding, cooling down, trades used)

→ Named int variables, or buy[]/sell[] arrays

Each day reads only yesterday: O(states) memory, no table.

Two strings: match, merge or count

→ boolean[][] / int[][] over prefixes, then one row

One cell per prefix pair; the row trick needs the dependency arrows (↑, ←, ↖).

Running sums that can be negative

→ Offset array (sum + total), or HashMap<Long, Integer>

Arrays are fastest when the range is small; a map handles anything.

"Last interval that ends before this one starts"

→ Sort by end + binary search, or TreeMap.floorEntry

O(log n) per job instead of scanning back.

Count palindromic substrings

→ Expand around 2n − 1 centres

Same O(n²) as the table, but no n² memory.

Two players, optimal play, on a range

→ int[][] lead filled by range length

One number per range; the minus sign does the opponent's thinking.

07 · recognise

Spot the pattern

Buy and sell with a cooldown, a fee, or at most k trades

State-machine DP: one variable per mode, one max() per arrow

"At most k" of anything (trades, deletions, operations)

Add the count to the state: dp[…][t] for t = 0..k

A pattern with '.' and '' must match the whole* string

Two-string boolean DP; '*' = zero copies (j − 2) or one more (i − 1)

Can s3 be formed by merging s1 and s2, keeping each one's order?

dp[i][j] over two prefixes: the next letter came from s1 or from s2

How many times does t appear as a subsequence of s?

Counting two-string DP: skip s[i] or use it; one row, j downward

Count (or find) palindromic substrings

Expand around all 2n − 1 centres

Put + or − before each number to hit a target; split into two groups by a difference

Subset count with P = (total + target) / 2

Jobs or intervals with a profit, no overlaps, maximise the total

Sort by end + DP + binary search for the last compatible job

All intervals are worth the same

Greedy by earliest end (Intervals chapter) — no DP needed

Two players take turns, "both play optimally"

Game DP: one 'lead' per state, opponent's best comes back with a minus sign

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

Reading a state you already overwrote today. In Cooldown, HOLD must use yesterday's REST and SOLD must use yesterday's HOLD — save the previous values first.
Starting HOLD at 0. That claims a free share. Use −∞ (Integer.MIN_VALUE / 2) or -prices[0].
Integer.MIN_VALUE as −∞, then hold + p - fee with p < fee: it wraps to a huge positive number and wins every max.
Regex: treating '*' as a wildcard on its own. It always belongs to the character before it — look at p[j − 1] and p[j − 2] together.
Regex: leaving row 0 all false. "ab" matches the empty text, so dp[0][j] = dp[0][j − 2] for a '*'.
Interleaving: skipping the m + n == s3.length() check — leftover letters in s3 then go unnoticed.
Distinct Subsequences in one row with j going UP: the same letter of s is used twice in one subsequence. Go down, as in 0/1 knapsack.
Target Sum: forgetting the parity and |target| ≤ total checks, or a loop that stops before s = x so zeros never double the count.
Job Scheduling: < instead of <= (touching jobs are allowed), or binary-searching an array that isn't sorted by the key you search.
Game DP: maximising your own score as if the opponent moved randomly. The opponent plays their best — that's the minus sign.

tricks

Draw the state machine before any code: circles for modes, arrows for moves. Then write exactly one line per arrow.
For two strings, say the state with prefixes in one sentence: "dp[i][j] = can the first i letters of s match the first j of p".
Signs, two groups, or a difference in the question? Try the algebra: P + N = total, P − N = target.
Bas itna yaad rakho: same value for every job → greedy; different values → sort by end + DP + binary search.
Game DP: write "my best lead". The opponent's best lead comes back from the recursion, and you subtract it.
Chalo, dry-run on 4–5 days or 3–4 letters first. Every family in this chapter fits on one page of paper.
After the table works, look at the dependency arrows (↑ ← ↖) to decide whether one row is enough and which way to loop.

09 · why & how

Questions you might be too shy to ask

How do I tell which DP family a new problem belongs to?

Ask what you must remember to make the next decision. A status that changes over time (holding, cooling down, trades used) → state machine. Positions in two strings → a prefix table. Signs or two groups → subset sum. Intervals with values → sort by end + binary search. Two players alternating → game DP on what's left. The answer to "what must I remember" is the state.

Why is the stock DP called a "state machine"?

Because at the end of each day you are in exactly one mode, and only some moves between modes are legal — like a Java thread's Thread.State. Draw the modes as circles and the legal moves (buy, sell, rest, cool down) as arrows. The DP keeps the best profit for every circle; each arrow becomes one Math.max. Cooldown adds a SOLD circle; a fee puts a cost on the sell arrow; k trades makes a chain of 2k circles.

In Stock III, why is it safe to update buy1, sell1, buy2, sell2 in place on the same day?

Using today's updated buy1 inside sell1 means "buy and sell on the same day", which earns exactly 0. So it can never create fake profit; it only lets a state copy a value it could already have. The same argument covers buy[t] and sell[t] in Stock IV.

Cooldown returns Math.max(sold, rest). Why is hold never the answer?

Ending in HOLD means you paid for a share and never sold it. That value is some earlier REST profit minus a price. REST never goes down over the days, so today's REST is at least as big, without the unsold share. So holding at the end is never better: skip that buy and you have at least as much.

Do I need to memorise all the stock problems?

No. Memorise the machine. Stock I is k = 1, Stock II is unlimited (CASH/HOLD), III is k = 2, IV is general k, Cooldown adds a SOLD state, Fee puts a cost on the sell arrow. If you can draw the circles, you can write any of them in a few minutes.

What's the difference between Regular Expression Matching (LC 10) and Wildcard Matching (LC 44)?

In LC 10, '' repeats the character before it ("a" = zero or more a's). In LC 44, '' alone matches any sequence and '?' matches one character. Same (m + 1) × (n + 1) table; only the '' rule changes: LC 44 uses dp[i][j − 1] (match nothing) || dp[i − 1][j] (eat one more).

When I squeeze a 2D table into one row, how do I know whether j goes up or down?

Look at what a cell reads. ↑ is dp[j] itself — the old value, always safe. If it also reads a cell to the left in the previous row (↖ dp[j − 1], or knapsack's dp[c − w]), go down, so that cell isn't overwritten yet: Distinct Subsequences, 0/1 knapsack. If it reads ← (dp[j − 1] from this row), go up: Interleaving String. Needs both ↖ and ← (LCS)? Keep ↖ in a separate variable before you overwrite it.

Distinct Subsequences' middle counts can overflow even a long. Why does an int solution still work?

The DP only adds. Java's int addition wraps around (it computes modulo 2³²), and sums modulo 2³² are still exact modulo 2³². If the true final answer fits in an int — LeetCode guarantees it — the wrapped result equals it. This only works because nothing compares, divides or takes a max of the middle values.

Expand-around-centre has no table. Why is Palindromic Substrings in a DP chapter?

It uses the DP fact: s[i..j] is a palindrome when its ends match and s[i+1..j−1] is one. The pal[i][j] table stores that for every pair. Expanding from a centre walks the same chain, inside → out, and stops at the first failure, so there is nothing to store. Same idea, same O(n²) time, O(1) memory.

Do I need Manacher's algorithm for interviews?

Rarely. Expand-around-centre (O(n²) time, O(1) memory) is the expected answer for Palindromic Substrings and Longest Palindromic Substring. Mention that Manacher's algorithm reaches O(n) by reusing the mirror image inside a known palindrome — that's usually enough.

Target Sum: why does a 0 in nums double the answer?

+0 and −0 are two different sign choices that give the same sum, and the problem counts both. The code does it by itself: for x = 0 the loop runs s = want down to s >= 0, so ways[s] += ways[s - 0] doubles every count. That's why the loop must go all the way to s >= x, not stop at s > x.

Why can't I use the greedy "earliest end first" from the Intervals chapter for Job Scheduling?

Greedy maximises the number of jobs, not their value. Jobs [1–10] paying 100 and three short jobs inside that time, paying 1 each: greedy takes the three short ones for 3; the best is 100. Once values differ, you need the DP's "skip or take" at every job.

Job Scheduling: why sort by end time and not by start time?

After sorting by end, the jobs that finish by this job's start are always a prefix of the list. best[k] already holds the best plan for that prefix, and one binary search finds k. Sorting by start also works, but then you fill from the right: skip this job, or take it plus the best plan from the first job starting at or after its end.

Why does the game DP store a difference instead of both players' scores?

The game is the same for whoever is to move, so one number — "how far ahead can the mover get" — describes a range completely. When you take nums[i], the opponent becomes the mover on the rest and gets ahead by lead[i + 1][j], so your lead is nums[i] − lead[i + 1][j]. Two scores would need two tables and a turn flag.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#309
Best Time to Buy and Sell Stock with Cooldownmust-do
MediumGoogleBloombergAmazonMicrosoft
#714
Best Time to Buy and Sell Stock with Transaction Fee
MediumBloombergGoogleMicrosoftAmazon
#123
Best Time to Buy and Sell Stock III
HardMicrosoftAmazonGoogleBloomberg
#188
Best Time to Buy and Sell Stock IVmust-do
HardAmazonGoogleMicrosoft
#10
Regular Expression Matchingmust-do
HardAirbnbByteDance / TikTokAmazonGoogleMeta+1
#97
Interleaving Stringmust-do
MediumAmazonMicrosoftGoogle
#115
Distinct Subsequences
HardSalesforceAmazonGoogleBloomberg
#647
Palindromic Substringsmust-do
MediumMetaWalmartAmazonMicrosoftGoogle
#494
Target Summust-do
MediumAmazonMetaGoogleMicrosoft
#1235
Maximum Profit in Job Schedulingmust-do
HardAirbnbAmazonMicrosoftGoogle
#486
Predict the Winner
MediumAmazonGoogle

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#121
Best Time to Buy and Sell Stock
Easyin Arrays & Strings
Stock I: one trade. Its running minimum is the k = 1 case of this chapter's machine.
#122
Best Time to Buy and Sell Stock II
Mediumin Arrays & Strings
Stock II: unlimited trades. Its cash/hold alternative is the two-state machine that Fee and Cooldown extend.
#416
Partition Equal Subset Sum
Mediumin Dynamic Programming
Target Sum's subset count is this problem with + instead of ||.
#5
Longest Palindromic Substring
Mediumin Dynamic Programming
The same 2n − 1 centres as Palindromic Substrings; keep the longest instead of counting.
#72
Edit Distance
Mediumin Dynamic Programming
The parent of every two-string table here: prefixes, base row and column, three neighbours.
#435
Non-overlapping Intervals
Mediumin Intervals
Job Scheduling with every job worth the same: greedy by end time, no DP.
#312
Burst Balloons
Hardin Dynamic Programming
Interval DP filled by range length, like the game table.
#131
Palindrome Partitioning
Mediumin Backtracking
Precompute pal[i][j] from this chapter so every palindrome check is O(1).

11 · revise

The whole chapter on one screen

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

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.
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".
template
Machine: save yesterday, then hold = max(hold, rest − p), sold = hold + p, rest = max(rest, sold). One line per arrow.
template
Two strings: dp[i][j] over prefixes. Regex '*': dp[i][j−2] || (fits && dp[i−1][j]). Interleave: from s1 (↑) or from s2 (←).
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.
trap
Never read a state you already changed today: save prev values first. Holding starts at −∞ (MIN_VALUE / 2), never 0.
trap
Weighted jobs: earliest-end greedy fails. Sort by end and binary-search jobs with end ≤ start (<=, not <).
pro tip
Target Sum: P = (total + target) / 2. Check parity and |target| ≤ total, then count subsets with a downward loop.
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.

12 · recall

Flip, remember, repeat

card 1 / 14

recall

What is state-machine DP, in one line?

tap or Space to flip ↻

Question 1: What is state-machine DP, in one line?

13 · check yourself

Quick quiz

In Stock with Cooldown (HOLD, SOLD, REST), which state does a buy come from?
Stock IV with k ≥ n/2. What is the answer?
Regex table: p[j − 1] is '*'. Which cells can make dp[i][j] true?
s = "" and p = "a*b*". Does it match?
nums add up to 10 and target = 4. The '+' group must add up to…
One-row Distinct Subsequences: why does j loop from n down to 1?
Jobs sorted by end time. For a job that starts at 5, what does the binary search find?
Why is there a minus in lead[i][j] = nums[i] − lead[i + 1][j]?
How many centres does expand-around-centre try for a string of length n?

0/0 correct · 9 left

14 · learn more