Dynamic Programming

01 / The shared mechanism

A table fills itself, one cell at a time — each entry composed from a constant number of earlier ones. The recurrence changes per sub-pattern, but the machinery — state, transition, fill order — is shared.

02 / The one-sentence essence

Each index occupies one of a small fixed set of states, with explicit rules for transitioning between them. Unroll the state machine across the input — the DP table has one row per state, one column per position.

Problemmax stock profit with cooldownPrices[1, 2, 3, 0, 2]

held

sold

rest

Three states per day: held (own a share), sold (just sold — cooldown applies tomorrow), rest (not holding, free to buy). Fill day by day.

step

0 / 14

writing

—

via

—

max profit

—

0 / 14

prices

03 / The pattern signature

# state-machine DP — track each state over timedp[state][0] ← base case per statefor i in 1..n−1:for each state:dp[state][i] ← max/min over valid transitions from state'of (dp[state'][i−1] + cost(state'→state, input[i]))return max over end states of dp[state][n−1]# cooldown: states = held / sold / rest# held[i] = max(held[i−1], rest[i−1] − price[i])# sold[i] = held[i−1] + price[i]# rest[i] = max(rest[i−1], sold[i−1])

04 / When to recognize this pattern

"finite modes"

The choices at each position depend on what mode you're in — holding vs not, consecutive vs broken streak, transaction count remaining. The mode is the state.

"transition constraints"

Some moves are illegal from some states — must rest before buying, can't skip two in a row, must alternate. The illegal transitions encode the problem's rules; the legal ones become the recurrence.

"answer at end is per-state"

The final answer is the best over terminal states at position n − 1. Often that's "not holding" — but sometimes the problem asks "must end in state X" and you only read one row.

"low constant state count"

Usually 2–5 states. When the state count grows with input (e.g., transaction count k), the DP gains an extra axis and the complexity becomes O(N · k).

05 / Common pitfalls

Missing or overlapping states.

If your states don't partition every possible position cleanly, transitions blow up and the recurrence becomes ambiguous. Sanity check: can every legal position at any point in time be assigned to exactly one state? If not, refine the state set before writing code.

ii.

Base-case asymmetry across states.

Each state needs its own day-0 value, and they're rarely all zero. For cooldown, held[0] = -price[0] (we bought today) while sold[0] = rest[0] = 0 (no transaction). Off-by-one bugs at the base propagate through every later cell.

iii.

Hidden coupling between states.

Reading dp[A][i-1] when filling dp[B][i] is fine, but reading dp[A][i] (same column) creates an order dependency: you must fill state A before state B within day i. Always sketch the transition graph and ensure your inner loop order respects it.

06 / Go practice — on LeetCode

Four problems across the state-machine family. The first three vary the state count and the cooldown/fee rules; the fourth shifts genre to non-stock problems where the state is "consecutive choices" rather than position.

01Best Time with Cooldown— LC 309medium→02Best Time with Fee— LC 714medium→03Best Time IV— LC 188hard→04Paint House— LC 256medium→

— / When to use which

1-D linear

Use when the answer at index i depends on a constant number of earlier indices.

house-robber · climbing-stairs · max-subarray

2-D grid

Use when the state has two indices — a grid, or two interacting sequences.

min-path · LCS · edit-distance

knapsack

Use when each item triggers a choose-or-skip decision under a capacity constraint.

subset-sum · coin-change · partition

interval

Use when the state is a range (i, j) and the answer composes from inner intervals.

palindrome · matrix-chain · burst-balloons

state machine

Use when each index can be in one of several finite states with rules for transitioning between them.

stock · cooldown · two-state