Bitmask DP: Traveling Salesman and Covering Problems

Core Philosophy

Use the binary bits of an integer to represent the status of a set. For a set of size $n$, there are $2^n$ possible states.

Common Bitwise Operators:

• state | (1 << i): Add item $i$ to the set (set bit $i$ to 1).
• state & ~(1 << i): Remove item $i$ from the set (set bit $i$ to 0).
• (state >> i) & 1: Check if item $i$ is in the set.
• state == (1 << n) - 1: Check if the set contains all elements.

Shortest Path Visiting All Nodes (LeetCode 847)

Given a graph with $n$ nodes ($n \le 12$), find the shortest path that visits every node. You can start and stop at any node, and revisit nodes.

BFS + Bitmask: Define state as (current_node, visited_mask).

public int shortestPathLength(int[][] graph) {
    int n = graph.length;
    int fullMask = (1 << n) - 1;
    Queue<int[]> queue = new LinkedList<>(); // [node, mask, distance]
    boolean[][] visited = new boolean[n][1 << n];
    
    for (int i = 0; i < n; i++) {
        queue.offer(new int[]{i, 1 << i, 0});
        visited[i][1 << i] = true;
    }
    
    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int node = curr[0], mask = curr[1], dist = curr[2];
        
        if (mask == fullMask) return dist;
        
        for (int next : graph[node]) {
            int nextMask = mask | (1 << next);
            if (!visited[next][nextMask]) {
                visited[next][nextMask] = true;
                queue.offer(new int[]{next, nextMask, dist + 1});
            }
        }
    }
    return -1;
}

Traveling Salesperson Problem (TSP)

Find the shortest route that visits $n$ cities exactly once and returns to the origin. (Typical constraint: $n \le 20$).

State: dp[mask][i] = Shortest distance to have visited the set mask, ending at city i.

public int solveTSP(int[][] dist) {
    int n = dist.length;
    int fullMask = (1 << n) - 1;
    int[][] dp = new int[1 << n][n];
    for (int[] row : dp) Arrays.fill(row, 100000000); // Infinity proxy
    
    dp[1][0] = 0; // Start at city 0
    
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            // If u is not in mask, skip
            if (((mask >> u) & 1) == 0) continue;
            
            for (int v = 0; v < n; v++) {
                // If v is already in mask, skip
                if (((mask >> v) & 1) == 1) continue;
                
                int nextMask = mask | (1 << v);
                dp[nextMask][v] = Math.min(dp[nextMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    // Return to starting city 0
    int minCycle = Integer.MAX_VALUE;
    for (int i = 1; i < n; i++) {
        minCycle = Math.min(minCycle, dp[fullMask][i] + dist[i][0]);
    }
    return minCycle;
}

Tiling Problems (Domino Covering)

Cover an $M \times N$ grid with $1 \times 2$ dominoes. Find the total number of ways ($M, N \le 11$).

Strategy: Compress the state of each column. dp[i][mask] represents the configuration of row-protrusions from column $i$ to column $i+1$.

• Precompute valid transitions between masks.
• Ensure no odd-length gaps exist after vertical domino placement.

Technical Summary Table

Ideal Constraints: Bitmask DP is generally applicable when part of the state involves a subset of elements and the set size $N \le 20$ (often $N \le 12$ for high-performance requirements). 筋