Choosing the state is the whole problem. Everything else is bookkeeping.
The rule
The state must capture everything about the past that affects the future, and nothing else.
Too little and the recurrence is wrong. Too much and the complexity explodes. Both failures are common; the second is more comfortable and more often fatal.
Diagnostic questions
- “If I described my situation to someone who must finish the job, what would I have to tell them?” That list is the state.
- “Does this parameter change any future decision?” If not, drop it.
- “Can I sort the input so a dimension disappears?” Sorting by one key often makes that key implicit.
- “Is something monotone?” Monotone quantities can often be binary-searched or greedily fixed instead of stored.
- “Can I replace ‘the set of things used’ with ‘how many things used’?” Only if the items are interchangeable — but when they are, this collapses to .
The standard state shapes
| Shape | Meaning | Typical problems |
|---|---|---|
dp[i] | best answer for a prefix of length | LIS, house robber, coin change, word break |
dp[i][j] | prefix of A, prefix of B | LCS, edit distance, string alignment |
dp[l][r] | an interval | matrix chain, burst balloons, palindromes |
dp[i][w] | first items, capacity | knapsack, subset sum |
dp[v] | subtree rooted at | tree DP |
dp[v][0/1] | subtree, with chosen or not | independent set on a tree, tree colouring |
dp[mask] | a subset already handled | TSP, assignment, set cover |
dp[mask][i] | subset handled, currently at | Held-Karp |
dp[pos][tight][...] | digits placed so far | digit DP |
dp[i][j][k] | position, resource, extra flag | almost every “with at most operations” problem |
dp[i][last] | position and last choice | no-two-adjacent, colouring a row |
dp[row][profile] | row-by-row grid fill | broken profile DP |
Techniques for shrinking the state
Drop what is derivable
If is always a function of and the other parameters, remove it. Example: if you always place items in order and the count determines the position, keep only the count.
Exchange a dimension for a value
Instead of dp[i][j] = is it possible, use dp[i] = the best achievable j. This turns a boolean table into a single array. The classic instance is LIS: rather than dp[i][len], keep tail[len] = smallest possible tail of an increasing subsequence of that length, which reduces to .
Sort to make a dimension implicit
Scheduling and interval problems almost always start with a sort. Once sorted by end time, “which jobs are still available” collapses to “the index we have reached”.
Use the structure of the objective
If the cost is a sum of independent contributions, you can often process contributions one at a time rather than tracking the whole configuration. The edge-contribution trick is this idea applied to trees.
Compress the value range
Coordinate compression shrinks a -sized dimension to when only distinct values ever occur.
When the state is too big
- Is the state space actually sparse? Use memoization with a hash map; only reachable states cost anything.
- Can the transition be batched? A segment tree or convex hull trick can replace an inner loop with — see DP optimizations.
- Can the DP be expressed as a matrix power? If the transition is linear and fixed, matrix exponentiation handles up to .
- Is one dimension convex? Slope trick represents an entire convex function in a heap.
- Is there a Lagrangian reformulation? Aliens trick removes a “exactly groups” dimension entirely.
A worked reduction
“Choose a subsequence of at most elements maximising the sum, with no two adjacent.”
- Naive state:
dp[i][k][mask of chosen]— hopeless. - Observation: only whether the previous element was chosen matters.
- State:
dp[i][j][0/1]= best using the first elements, chosen, last element taken or not. states, transition.
The move from “the set of chosen elements” to “was the previous one chosen” is the archetypal state reduction.
See also: Introduction to DP · DP Cheatsheet · Space Optimization