DP Bitmasking
Bitmasking DP is used for problems where the state is a subset of items (e.g., traveling salesman problem). Each subset is represented as a bitmask of size n, and we store DP[mask][last] to represent optimal value.
Example: Traveling Salesman Problem (TSP) – find the shortest path visiting all cities exactly once and returning to start. DP[mask][i] = min over j of DP[mask without i][j] + dist[j][i].
Java implementation skeleton:
int n = 4;
int[][] dp = new int[1 << n][n]; // large values initialization
for (int mask = 1; mask < (1 << n); mask++) {
for (int last = 0; last < n; last++) {
if ((mask & (1 << last)) == 0) continue;
int prevMask = mask ^ (1 << last);
if (prevMask == 0) dp[mask][last] = dist[0][last];
else {
for (int prev = 0; prev < n; prev++) {
if ((prevMask & (1 << prev)) != 0) {
dp[mask][last] = Math.min(dp[mask][last], dp[prevMask][prev] + dist[prev][last]);
}
}
}
}
}
int fullMask = (1 << n) - 1;
int answer = dp[fullMask][0]; // with return to start (if needed)
Bitmasking DP is used for subset problems like TSP, minimum set cover, partition, etc.
Two Minute Drill
- Bitmasking DP stores subsets as integer masks.
- State DP[mask][i] means best solution for subset mask ending at i.
- Time O(2^n * n²) typical.
- Used when n ≤ 20-25 due to exponential state space.
Need more clarification?
Drop us an email at career@quipoinfotech.com