Bitmask DP

Assignment Problem

Assign n tasks to n workers, one each, minimizing cost. dp[mask] = min cost when the set of workers in 'mask' have been assigned. For each new task, try assigning it to any unassigned worker.

O(n * 2^n)

O(2^n)

How It Works

The assignment problem matches n tasks to n workers, one each, at minimum total cost. Bitmask DP exploits a key observation: if you assign tasks in order 0, 1, 2, ..., then after processing some tasks the only thing that matters is which workers are taken — captured by dp[mask], the minimum cost of assigning the first popcount(mask) tasks to exactly the workers in mask. To extend, give task popcount(mask) to any free worker w: dp[mask | (1<<w)] = min(itself, dp[mask] + cost[popcount(mask)][w]).

Because the task index is implied by the mask's popcount, one dimension disappears, leaving O(2^n) states with O(n) transitions each — O(2^n × n) time. That beats the n! brute force decisively and handles n up to about 20; larger instances call for the polynomial Hungarian algorithm.

Step-by-Step Visualization

Assign tasks to workers using bitmask DP

mask=0000No tasks assigned

1/3

Code

Java

static int assignmentProblem(int[][] cost) {
  int n = cost.length;
  int[] dp = new int[1 << n];
  Arrays.fill(dp, Integer.MAX_VALUE);
  dp[0] = 0;

  for (int mask = 0; mask < (1 << n); mask++) {
    int worker = Integer.bitCount(mask);
    if (worker >= n) continue;
    for (int task = 0; task < n; task++) {
      if ((mask & (1 << task)) != 0) continue;
      int next = mask | (1 << task);
      dp[next] = Math.min(dp[next], dp[mask] + cost[worker][task]);
    }
  }
  return dp[(1 << n) - 1];
}

Tips & Gotchas

1dp[mask] = min cost when the set of assigned tasks is 'mask'

2Bit i in mask = 1 means task i is assigned

3Count set bits to know which worker is next

Practice Problems

1Minimum XOR Sum of Two Arrays
2Maximum Compatibility Score Sum
3Minimum Number of Work Sessions to Finish the Tasks
4Fair Distribution of Cookies

About the Bitmask DP Pattern

Use a binary number (bitmask) to represent which items have been selected. Bit i is 1 if item i is chosen. This lets you track subsets as DP states — the mask IS the state. Works when n ≤ ~20.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

Climbing Stairs
Coin Change
Longest Common Subsequence
0/1 Knapsack
Edit Distance
House Robber
Longest Increasing Subsequence
Word Break

Frequently Asked Questions

Why can the task index be dropped from the state?

Tasks are processed in a fixed order, so a mask with k bits set always corresponds to the first k tasks being assigned. The popcount of the mask reconstructs the task index for free, halving the state dimensions compared to a naive dp[task][mask].

How does this compare to the Hungarian algorithm?

Bitmask DP runs in O(2^n · n) and is short to implement, but only works for n up to about 20. The Hungarian algorithm solves the same problem in O(n^3) for any size, at the cost of substantially more implementation effort. In interviews, bitmask DP is almost always the expected answer.

Can this template handle workers taking multiple tasks?

Yes, with modifications: the mask then tracks which tasks are done rather than which workers are used, and transitions assign a whole subset or the next task to some worker. Problems like Work Sessions enumerate submasks or add a capacity component to the state.