Bitmask DP

Use an integer's bits as a set of chosen items, so you can run DP over subsets when n is at most about 20 - assignment problems and the travelling salesman.

45 minCF 1800–22005 interactive10 problems

The problem

Some problems ask you to use each item from a small set exactly once, in some order: assign n jobs to n workers, or visit n cities. Brute force tries all $n!$ orders. For $n = 20$ that is about $2.4 \cdot 10^{18}$ , impossible.

But the future of such a search depends only on which items are already used, not on the order they were used in. There are only $2^n$ sets. That is a DP over subsets.

1 of 8