Submask DP
Submask DP
Submask DP is a bitmask technique where, for a fixed mask, we iterate through all of its submasks efficiently.
Core Trick: Iterate all submasks of a mask
For a mask m, this loop goes through all non-zero submasks of m:
If you also need submask 0, process it separately.
Why it works?
s - 1changes the lowest set bit and all bits after it& mremoves bits not in the original mask- so we stay inside submasks of
m
Complexity Fact (very important)
If you run the submask loop for every mask, total complexity is:
Reason: for each bit, there are 3 choices:
- not in mask
- in mask but not in submask
- in both mask and submask
Example: Partition a set into valid groups
Suppose:
ok[s]tells whether subsetsis a valid group- We want minimum number of groups to cover mask
m
Let: