Lesson 32.4 · Advanced DP
Bitmask DP over Subsets
For up to about 20 items, an int mask records which items are used. dp[mask] (or dp[mask][last]) has 2ⁿ states.
12 min
Think of it like this
A row of light switches: each pattern of on/off switches is a number. Visiting every pattern is visiting every subset.
1.Masks as sets
Bit i of mask is 1 if item i is in the set. Add item i: mask | (1 << i). Test: (mask >> i) & 1. Size: Integer.bitCount(mask). All items: (1 << n) − 1.
Typical states: dp[mask] (assignments, partitions) or dp[mask][last] (visiting nodes, travelling salesman, O(2ⁿ × n²)). With n = 16 that's about 65 000 masks: fine. With n = 30, a billion: too many.
public class Main {
public static void main(String[] args) {
char[] items = {'a', 'b', 'c'};
int n = items.length;
for (int mask = 0; mask < (1 << n); mask++) {
StringBuilder set = new StringBuilder();
for (int i = 0; i < n; i++)
if (((mask >> i) & 1) == 1) set.append(set.length() > 0 ? ", " : "").append(items[i]);
String bits = String.format("%3s", Integer.toBinaryString(mask)).replace(' ', '0');
System.out.println(bits + " {" + set + "}");
}
}
}Output
000 {}
001 {a}
010 {b}
011 {a, b}
100 {c}
101 {a, c}
110 {b, c}
111 {a, b, c}Remember
- n ≤ ~20.
- dp[mask] or dp[mask][last].
- Increasing mask order works when transitions add bits.
Common mistakes
- Operator precedence: write (mask >> i) & 1 with parentheses.