← DP Patterns · guided lesson
DP Patterns
the story
State-machine DP
Every tool here exists because something was too slow or broke without it. Here is what.
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 solved
Choosing 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.
why it matters: 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.
sources: Bellman — On the Theory of Dynamic Programming (PNAS, 1952) ↗ · Viterbi — Error bounds for convolutional codes and an asymptotically optimum decoding algorithm (IEEE Trans. Information Theory, 1967) ↗ · Forney — The Viterbi Algorithm: A Personal History (arXiv, 2005) ↗
also in this chapter: Regular-expression matching · Palindromic substrings: centres, tables and Manacher · Knapsack in disguise: signs to a subset sum · Weighted interval scheduling (sort + DP + binary search) · Game DP (minimax on what's left)
the idea
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.
watch it
State machine: buy, sell, cool down
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
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.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
At most k trades: a chain of states
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
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.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 10
Read it once. Say it out loud once. Bas.
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.
key idea 2 of 10
Read it once. Say it out loud once. Bas.
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.
key idea 3 of 10
Read it once. Say it out loud once. Bas.
"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.
key idea 4 of 10
Read it once. Say it out loud once. Bas.
Impossible states start at −∞ (Integer.MIN_VALUE / 2 in Java), never at 0 — a 0 in HOLD would mean a free share.
key idea 5 of 10
Read it once. Say it out loud once. Bas.
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 +).
key idea 6 of 10
Read it once. Say it out loud once. Bas.
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.
key idea 7 of 10
Read it once. Say it out loud once. Bas.
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.
key idea 8 of 10
Read it once. Say it out loud once. Bas.
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.
key idea 9 of 10
Read it once. Say it out loud once. Bas.
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.
key idea 10 of 10
Read it once. Say it out loud once. Bas.
Cost is still states × work per state: stocks n·(states), strings m·n, target sum n·P, scheduling n·log n, games n².
spot the pattern
When you see this, think this
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
+6 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- 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].
quick check
One question. No pressure.
In Stock with Cooldown (HOLD, SOLD, REST), which state does a buy come from?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Best Time to Buy and Sell Stock with Cooldown
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
What is state-machine DP, in one line?
Question 1: What is state-machine DP, in one line?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.