DP Cheatsheet¶

Use this page when the state is close, but you still need to stabilize what each transition is allowed to remember.

Do Not Use When¶

the problem is already greedy after sorting or scanning
the real blocker is a missing graph / number-theory observation
you still cannot say what the state forgets and what it must preserve

Choose By Signal¶

best answer on a prefix -> 1D DP
extra small parameter on a prefix -> 2D or layered DP
decimal representation with tight bound -> Digit DP hot sheet
shrinking subarray / interval -> interval DP
subtree choices combine upward -> tree DP
subsets or masks are the natural state -> bitmask DP
one full mask cube needs all-submask or all-superset aggregates -> SOS DP hot sheet
two full mask functions combine by xor, or one exact subset split inside each mask is the real bottleneck -> FWHT / XOR Convolution / Subset Convolution hot sheet
one huge boolean sum axis or component-size reachability row where word-packed shift-OR is the real implementation win -> Bit-Parallelism / Bitset Optimization hot sheet
one grid dimension is small and the state is the current frontier -> Broken Profile hot sheet
partition prefixes into groups with monotone best split points -> Divide and Conquer DP hot sheet
split-point interval DP with additive interval cost and monotone opt windows -> Knuth Optimization hot sheet
affine transition m * x + b over previous states -> CHT / Li Chao hot sheet
one convex function over coordinate x is updated by hinge penalties or bounded argmin shifts -> Slope Trick hot sheet
exact K picks / segments become cheap after charging one integer penalty per use -> Aliens Trick hot sheet

State Checklist¶

what has been processed?
what still matters?
does the state forget any information needed later?

Transition Checklist¶

are all legal next moves covered?
are any cases counted twice?
what iteration order respects dependencies?

Common Forms¶

dp[i] = best answer on the first i elements
dp[i][j] = answer on prefix i with extra parameter j

Retrieval Cues¶

value or feasibility over prefixes -> classic 1D DP
tree structure decides the subproblems -> tree DP
digits with tight constraints -> Digit DP hot sheet
intervals shrink from both ends -> interval DP
moving window contributes a min / max / median -> combine DP thinking with a window structure
the answer for each mask needs all of its submasks or supersets -> SOS DP hot sheet
the answer needs one full-cube xor convolution or one subset-convolution family route -> FWHT / XOR Convolution / Subset Convolution hot sheet
the DP is still boolean feasibility, but one wide sum axis should be packed and shifted wordwise -> Bit-Parallelism / Bitset Optimization hot sheet
local placements only depend on a small grid frontier -> Broken Profile hot sheet
one last segment k + 1 .. i plus monotone argmins -> Divide and Conquer DP hot sheet
one interval [l, r], one split k, plus cost(l, r) only -> Knuth Optimization hot sheet
previous states become lines and current states become one query point -> CHT / Li Chao hot sheet
the DP state itself is one convex piecewise-linear function of x -> Slope Trick hot sheet
the expensive exact-count dimension disappears after penalizing each use by lambda -> Aliens Trick hot sheet

Core Invariant¶

The state must remember exactly the information needed for future decisions, and nothing more.

If two histories are indistinguishable for all future transitions, they should collapse into the same state.

Window-Flavored DP¶

Useful snippets when a DP or greedy transition needs the best value over a recent window:

monotone minimum -> monotonic-deque-min.cpp
lower median / balanced split -> sliding-median-two-multisets.cpp

Repo anchor:

Safety Checks¶

base case
final answer location
overflow type
reconstruction needs parent or choice arrays

Main Trap¶

The classic DP bug is not syntax. It is a state that silently throws away information the future still needs, or an iteration order that reads values before they are ready.