Algorithms / State Compression Dp

Least You Need to Know: State-Compression DP, Bitmasks, and Small-Set Subproblems

State-compression DP works when the hard part of the problem is which small subset has already been used. Bitmasks make subset state compact, and the art is choosing what extra coordinate—such as current endpoint or last chosen item—must accompany the mask.

The least you need to know

A bitmask compactly records which elements of a small set are already chosen or visited.
State-compression DP is practical when the subset universe is small enough for `2^n` states.
Transitions usually add or remove one bit or iterate through submasks.
Many routing and assignment problems use states like `(mask, last)`.
The right complexity target is often `O(n 2^n)` or `O(n^2 2^n)`, which is feasible only for small `n`.

Key notation

mask bitset describing a chosen subset

(mask, last) subset plus current endpoint or last item

sub = (sub-1) & mask iterate through submasks of `mask`

Tiny worked example

In a traveling-salesperson-style DP, `dp[mask][last]` stores the best cost to visit exactly the cities in `mask` and end at `last`.
A transition adds one new city to the mask.
The subset is small, but the bitmask lets you store and update all visited sets compactly.

Common mistakes

The method is powerful only when the subset size is small; `2^n` grows too quickly otherwise.
A mask alone is often not enough because the future cost depends on where you currently are.
Bit operations are implementation details; the real design question is what state information is necessary.

How to recognize this kind of problem

The prompt asks about visiting or assigning a small number of elements in different orders or subsets.
The natural state is a used-set plus one extra coordinate such as current node, last choice, or remaining group.
A naive search would explore permutations, but repeated subproblems suggest memoization over subsets.