Dynamic Programming • State Compression

Bitmask DP

Represent small sets using integers (bitmasks) to solve problems like the Assignment Problem or TSP.

Overview

In problems with small constraints (e.g., N ≤ 20), we can represent a subset of items as bits in an integer. This is called a bitmask.

We want to assign N workers to N tasks with minimum cost. The mask represents which tasks are already assigned.

If task j is not in the mask `(mask & (1 << j) == 0)`, we transition to `mask | (1 << j)` by assigning the next available worker to task j.

The number of set bits in the mask equals the number of workers we've already assigned. We don't need a separate dimension for workers.

Cost Matrix (3x3, comma separated):

0000

001inf

010inf

011inf

100inf

101inf

110inf

111inf

Code Tracker

:::

1let dp = Array(1 << N).fill(Infinity); dp[0] = 0;

2for (let mask = 0; mask < (1 << N); mask++) {

3 let worker = countSetBits(mask);

4 for (let task = 0; task < N; task++) {

5 if (!(mask & (1 << task))) {

6 dp[mask | (1 << task)] = Math.min(

7 dp[mask | (1 << task)],

8 dp[mask] + cost[worker][task]

9 );

10 }

11 }

12}