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
State is a subset of items, encoded as a bitmask. Each transition adds one item to the set. The trick is recognising that the order in which items were chosen doesn't matter — only which subset — collapsing anN!search to2^Ndistinct states.
Problemmin cost assignment of N tasks to N workersInputcost = [7, 4, 3, 3, 1, 2, 5, 8, 6]
cost
7T0·W0
4T0·W1
3T0·W2
3T1·W0
1T1·W1
2T1·W2
5T2·W0
8T2·W1
6T2·W2
dp[mask]
0000
∞001
∞010
∞011
∞100
∞101
∞110
∞111
dp[mask] = min cost to assign tasks 0..popcount(mask)−1 to the workers indicated by mask. Start with dp[0] = 0, everything else ∞. Fill in popcount order over 2^3 masks.
step
0 / 32
mask
—
masks filled
1 / 8
dp[full]
∞
0 / 32
03 / The pattern signature
# assignment problem — fill in popcount-increasing orderdp[0] ← 0dp[mask] ← ∞ for mask ≠ 0for mask in 0..(2^N − 1):k ← popcount(mask) # next item indexfor j in 0..N−1 if j not in mask:dp[mask | (1 << j)] ← min(dp[mask | (1 << j)], dp[mask] + cost[k][j])return dp[(1 << N) − 1] # every item placed
04 / When to recognize this pattern
"N ≤ 20"
A constraint that says N is small (typically 15–20) where the answer requires checking every subset — a strong hint that
2^N states are tractable."choose all / assign each"
Phrases like "assign every task to a worker", "visit every node", "cover every skill" — the answer depends on which subset has been chosen, not the order.
"min / max / count over permutations"
When the naive answer is "try all
N! permutations", and the cost decomposes one element at a time, bitmask DP shares prefixes and collapses to 2^N · N."hamiltonian / TSP"
Held-Karp shape:
dp[mask][i] = min cost path visiting nodes in mask ending at i. The extra i dimension is needed when transition cost depends on the last item, not just the set.05 / Common pitfalls
Iterating masks in the wrong order.
You must visit
dp[mask] before any dp[mask | bit] is written to (forward DP) — natural since mask < mask | bit, so plain ascending iteration works. But for problems where the transition goes both ways or removes bits, sort masks by popcount instead.Forgetting the popcount → item-index mapping.
A common framing is "the k-th item to be placed is at position
popcount(mask)". Get this off-by-one wrong and you assign the same item twice (or skip one) without any error — just a wrong answer.Treating the mask as an ordered sequence.
The mask records which items are in the set, not the order they were added. If the answer depends on order (e.g., "last item visited"), you need an extra
i dimension — pure mask isn't enough.Iterating
j over mask instead of ~mask.A frequent typo: looping over set bits when you wanted unset bits (or vice-versa). Use
if (mask & (1 << j)) to check membership; flip the test for the other direction.06 / Go practice — on LeetCode
medium8
01Can I Win— LC 464→02Matchsticks to Square— LC 473→03Beautiful Arrangement— LC 526→04Partition to K Equal Sum Subsets— LC 698→05Campus Bikes II— LC 1066→06Maximum Compatibility Score Sum— LC 1947→07Minimum Number of Work Sessions to Finish the Tasks— LC 1986→08Fair Distribution of Cookies— LC 2305→
hard12
01Stickers to Spell Word— LC 691→02Shortest Path Visiting All Nodes— LC 847→03Find the Shortest Superstring— LC 943→04Number of Squareful Arrays— LC 996→05Smallest Sufficient Team— LC 1125→06Maximum Students Taking Exam— LC 1349→07Parallel Courses II— LC 1494→08Distribute Repeating Integers— LC 1655→09Minimum Incompatibility— LC 1681→10Find Minimum Time to Finish All Jobs— LC 1723→11Maximize Score After N Operations— LC 1799→12Minimum XOR Sum of Two Arrays— LC 1879→
— / 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
tree DP
Use when the problem lives on a tree and each node's answer depends on its children's answers.
house-robber-III · diameter · max-path-sum
bitmask
Use when state is a subset of items (typically
N ≤ 20) and only which items have been chosen matters — not the order.assignment · TSP · sufficient-team