Chapter 64

Home

Refactoring: State Compression DP

When the DP state includes a subset, storing it as a boolean array or set is wasteful. Bitmask representation — each bit = one element — compresses the state into a single integer. This is the key to solving NP-hard problems like the travelling salesman problem (TSP) for N ≤ 20.

Before: Set-Based State (Slow)

C++ — TSP with unordered_set state (impractical)

// State = "which cities have I visited?"
// Storing this as a set or boolean array:
//   - Copying the state is O(N)
//   - Hashing a set is expensive
//   - Memoisation key is complicated

// N=10 works, but N=20 is 1M states × O(N) copy = too slow

After: Bitmask State (Efficient)

A bitmask is an integer where bit i = 1 means "element i is included." dp[mask][last] = minimum cost to visit the set of cities in mask, ending at city last.

C++ — TSP with bitmask DP (O(N² × 2ᴺ))

int tsp(vector>& dist) {
    int n = dist.size();
    vector> dp(1 << n, vector(n, INT_MAX / 2));
    dp[1][0] = 0;  // start at city 0, only city 0 visited

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int last = 0; last < n; last++) {
            if (!(mask & (1 << last))) continue;
            for (int next = 0; next < n; next++) {
                if (mask & (1 << next)) continue;
                int new_mask = mask | (1 << next);
                dp[new_mask][next] = min(dp[new_mask][next],
                    dp[mask][last] + dist[last][next]);
            }
        }
    }

    int full = (1 << n) - 1;
    int ans = INT_MAX;
    for (int i = 1; i < n; i++)
        ans = min(ans, dp[full][i] + dist[i][0]);  // return to start
    return ans;
}

// N=20:  1M states × 20 transitions = 20M operations → ~0.2s

Rust — TSP with bitmask DP

fn tsp(dist: &[Vec]) -> i32 {
    let n = dist.len();
    let inf = i32::MAX / 2;
    let mut dp = vec![vec![inf; n]; 1 << n];
    dp[1][0] = 0;

    for mask in 1..(1 << n) {
        for last in 0..n {
            if mask & (1 << last) == 0 { continue; }
            for next in 0..n {
                if mask & (1 << next) != 0 { continue; }
                let new = mask | (1 << next);
                dp[new][next] = dp[new][next].min(
                    dp[mask][last] + dist[last][next]);
            }
        }
    }

    let full = (1 << n) - 1;
    (1..n).map(|i| dp[full][i] + dist[i][0]).min().unwrap()
}

💡 Bitmask DP limitations

N ≤ 20 for O(N² × 2ᴺ) DP. N ≤ 25 is possible with meet-in-the-middle. For N ≥ 30, you need approximation algorithms — DP is no longer feasible (2³⁰ is ~10⁹ states). Always check N before writing bitmask DP.

Key Takeaways

Practice