Bitmask DP
Dynamic programming over subsets when the state is a small visited set, partition, or compatibility frontier.
Bitmask DP
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Bitmask DP appears when the state is a small subset and the transition depends on which elements have already been taken. The size limit is strict, but within that range the technique is extremely expressive.
When to Use It
Use bitmask DP when:
\(n\) is small enough that \(2^n\) states are plausible,
the state is ``which items are already used'',
transitions depend on the last chosen item, the next free item, or a submask split.
Core Idea
Represent the chosen set by a mask. Then define a DP state such as: \[ dp[mask][last] = \text{best answer after visiting exactly the items in } mask \text{ and ending at } last. \]
Key Insight
The technique works because the mask compresses an exponential family of subsets into array indices. That turns ``visited-set'' recursion into an iterative DP over masks.
Operations / Main Technique
choose a subset state,
iterate masks in increasing order,
transition by adding one new bit or splitting into submasks.
Worked example.
In TSP-style DP, from state \((mask, last)\), try every city \(\texttt{nxt}\) not in \(\texttt{mask}\) and transition to \((mask \cup \{nxt\}, nxt)\).
Correctness Intuition
Each mask encodes exactly which decisions have already been made. The transition adds one legal next decision, so every valid configuration is reached from smaller subsets, and every DP value is built from the relevant previous states.
Complexity Analysis
Many standard forms run in \(O(n 2^n)\) or \(O(n^2 2^n)\), with \(O(n 2^n)\) memory.
Implementation
The code shows an assignment-style bitmask DP where \(\texttt{dp[mask]}\) tracks the best cost after assigning the first \(\texttt{popcount(mask)}\) rows to the chosen columns.
Common Pitfalls
Starting bitmask DP when \(n\) is already too large.
Forgetting whether the transition depends on set size, last item, or both.
Writing \(O(3^n)\) subset loops when \(O(n 2^n)\) would be enough.
Variants / Extensions
TSP / Hamiltonian path DP.
SOS DP and subset convolution.
State-compression DP on grids.
Practice Problems
Assignment or matching on \(n \le 20\).
Traveling salesman on a small graph.
Partition a small set into compatible groups.
References
Code
Contest-ready reference implementation for the idea explained above.
long long assignment_dp(const vector<vector<long long>>& cost) {
int n = (int)cost.size();
const long long INF = (long long)4e18;
vector<long long> dp(1 << n, INF);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); ++mask) {
int row = __builtin_popcount((unsigned)mask);
if (row >= n) continue;
for (int col = 0; col < n; ++col) {
if ((mask >> col) & 1) continue;
int next_mask = mask | (1 << col);
dp[next_mask] = min(dp[next_mask], dp[mask] + cost[row][col]);
}
}
return dp[(1 << n) - 1];
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.