State DP

Bitmask DP uses bit manipulation to represent subsets as integers. Each bit indicates whether an element is included.

Bitmask Basics

// Represent subset using integer bitmask
int mask = 0;
mask |= (1 << i);      // Add element i to subset
mask &= ~(1 << i);     // Remove element i from subset
mask ^= (1 << i);      // Toggle element i in subset
boolean has = (mask & (1 << i)) != 0;  // Check if element i is in subset

// Iterate through all subsets
for (int mask = 0; mask < (1 << n); mask++) {
    // mask represents a subset
}

Traveling Salesman Problem (TSP)

Find shortest route visiting all cities exactly once and returning to start.

// dp[mask][i] = min cost to visit cities in mask, ending at city i
public int tsp(int[][] dist) {
    int n = dist.length;
    int[][] dp = new int[1 << n][n];
    
    // Initialize with infinity
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
    
    // Base case: start at city 0
    dp[1][0] = 0;  // mask = 1 (only city 0), at city 0, cost = 0
    
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (dp[mask][u] == Integer.MAX_VALUE) continue;
            if ((mask & (1 << u)) == 0) continue;  // u must be in mask
            
            // Try visiting unvisited city v
            for (int v = 0; v < n; v++) {
                if ((mask & (1 << v)) != 0) continue;  // v not visited
                
                int newMask = mask | (1 << v);
                dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    // Return to start
    int fullMask = (1 << n) - 1;
    int result = Integer.MAX_VALUE;
    for (int u = 0; u < n; u++) {
        result = Math.min(result, dp[fullMask][u] + dist[u][0]);
    }
    
    return result;
}

TSP Trace Example

Cities: 4, dist matrix given
States: 2^4 = 16 masks

mask=0001 (city 0 visited): dp[1][0] = 0
mask=0011 (cities 0,1): dp[3][1] = dist[0][1]
mask=0111 (cities 0,1,2): dp[7][2] = min(dp[3][1]+dist[1][2], ...)
mask=1111 (all cities): dp[15][3] = min cost to visit all, end at 3

Answer: min over u of dp[15][u] + dist[u][0]

Assignment Problem

Assign n tasks to n workers with minimum cost.

// dp[mask] = min cost to assign tasks in mask
public int minAssignmentCost(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 taskCount = Integer.bitCount(mask);
        if (taskCount >= n) continue;
        
        for (int task = 0; task < n; task++) {
            if ((mask & (1 << task)) != 0) continue;  // Task already assigned
            
            int newMask = mask | (1 << task);
            dp[newMask] = Math.min(dp[newMask], dp[mask] + cost[taskCount][task]);
        }
    }
    
    return dp[(1 << n) - 1];
}

Complexity

• Time: O(2^n * n^2) for TSP
• Space: O(2^n * n) for TSP
• Works for n <= 20 (2^20 ≈ 1M states)

Some problems require tracking multiple state variables simultaneously.

House Robber II (Circular)

Houses are arranged in a circle. Adjacent houses cannot both be robbed.

// Break circle by considering two cases:
// Case 1: Include house 0, exclude house n-1
// Case 2: Exclude house 0, include house n-1
public int rob(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    
    return Math.max(robRange(nums, 0, n - 2),
                    robRange(nums, 1, n - 1));
}

private int robRange(int[] nums, int start, int end) {
    int prev2 = 0, prev1 = 0;
    for (int i = start; i <= end; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Best Time to Buy and Sell Stock with Cooldown

// State machine DP: hold, sold, cooldown
public int maxProfit(int[] prices) {
    int n = prices.length;
    if (n <= 1) return 0;
    
    int hold = -prices[0];  // Maximum profit holding a stock
    int sold = 0;           // Maximum profit just sold
    int cooldown = 0;       // Maximum profit in cooldown
    
    for (int i = 1; i < n; i++) {
        int prevHold = hold;
        int prevSold = sold;
        int prevCooldown = cooldown;
        
        hold = Math.max(prevHold, prevCooldown - prices[i]);
        sold = prevHold + prices[i];
        cooldown = Math.max(prevCooldown, prevSold);
    }
    
    return Math.max(sold, cooldown);
}

Paint House II (K Colors)

// Paint n houses with k colors, adjacent houses different colors
// Find minimum cost
public int minCostII(int[][] costs) {
    int n = costs.length, k = costs[0].length;
    
    int prevMin1 = 0, prevMin2 = 0;  // Two smallest costs
    int prevColor1 = -1;              // Color with minimum cost
    
    for (int i = 0; i < n; i++) {
        int currMin1 = Integer.MAX_VALUE, currMin2 = Integer.MAX_VALUE;
        int currColor1 = -1;
        
        for (int j = 0; j < k; j++) {
            int cost = costs[i][j] + (j == prevColor1 ? prevMin2 : prevMin1);
            
            if (cost < currMin1) {
                currMin2 = currMin1;
                currMin1 = cost;
                currColor1 = j;
            } else if (cost < currMin2) {
                currMin2 = cost;
            }
        }
        
        prevMin1 = currMin1;
        prevMin2 = currMin2;
        prevColor1 = currColor1;
    }
    
    return prevMin1;
}

State Machine DP Pattern

// Model problem as state machine with transitions
// States: S1, S2, ..., Sk
// At each step, you can transition between states
// dp[i][state] = max/min value at step i in state

// Generic template:
int[][] dp = new int[n + 1][numStates];
for (int i = 1; i <= n; i++) {
    for (int state = 0; state < numStates; state++) {
        for (int prevState : validPrevStates(state)) {
            dp[i][state] = optimize(dp[i][state], dp[i-1][prevState] + transition(state));
        }
    }
}
return optimize over final states of dp[n][state];

When to Use Multi-State DP

• Problem has multiple "modes" or "phases"
• Decisions depend on previous state (not just position)
• Need to track multiple attributes simultaneously
• State transitions form a graph/machine