Bit-mask DP
The main loop:for (int mask = 0; mask < (1 << n); ++mask)
In the memoization process:go(mask);
for (int i = mask; i != 0; i = (i - 1) & mask)
// the status transformation
For a certain bit which is 1 in mask, all possible combinations of lower 1 bits are enumerated, ending in all 0s. Then this bit becomes 0 with other initial lower 1 bits recovered by the bit-wise and. Again combinations of those bits are enumerated, ending in all 0s, while this bit remains 0.
No comments:
Post a Comment