Advanced Bitmask DP

May 2026 · 30 min read

Basic bitmask DP stores a subset as a state. Advanced bitmask DP uses masks to represent boundaries, compressed graph states, connectivity, or one half of a meet-in-the-middle split. These patterns are common in ICPC-style problems and hard Codeforces rounds.

Profile DP

Profile DP scans a grid cell by cell or row by row. A mask represents the current frontier: which cells in the next few positions are already occupied or connected.

// Domino tiling sketch: recursively fill one row profile.
void gen(int col, int cur, int next, vector<pair<int,int>>& trans) {
    if (col == W) {
        trans.push_back({cur, next});
        return;
    }
    if (cur & (1 << col)) {
        gen(col + 1, cur, next, trans);
        return;
    }
    // vertical domino affects next row
    gen(col + 1, cur | (1 << col), next | (1 << col), trans);
    // horizontal domino inside current row
    if (col + 1 < W && !(cur & (1 << (col + 1)))) {
        gen(col + 2, cur | (1 << col) | (1 << (col + 1)), next, trans);
    }
}

Connected Subset DP

Some graph problems require DP over subsets that form connected components. Precompute connectivity or grow states only by adding adjacent vertices.

bool connected[1 << N];
connected[0] = false;
for (int mask = 1; mask < (1 << N); ++mask) {
    int v = __builtin_ctz(mask);
    int rest = mask ^ (1 << v);
    connected[mask] = rest == 0 || ((adj[v] & rest) && connected[rest]);
}

The exact recurrence depends on the graph property, but the idea is always to avoid considering impossible disconnected states.

Meet-in-the-Middle with Masks

When n is around 40, 2^n is impossible but 2^(n/2) is feasible. Split the items into two halves, enumerate each half, then combine.

vector<long long> sums(vector<int> a) {
    int n = a.size();
    vector<long long> out;
    for (int mask = 0; mask < (1 << n); ++mask) {
        long long s = 0;
        for (int i = 0; i < n; ++i)
            if (mask & (1 << i)) s += a[i];
        out.push_back(s);
    }
    return out;
}

Memory Optimization

• Use rolling arrays when transitions only depend on the previous layer.
• Store int instead of long long when values fit.
• Use sparse maps when only a small fraction of states is reachable.
• Group masks by popcount to avoid scanning invalid layers.

Pruning and Dominance

In many state-compression searches, one state dominates another if it has the same mask and a better cost/resource tuple. Keep only the best representative.

// Example: dp[mask] = minimum cost seen for this exact mask.
if (new_cost < dp[new_mask]) {
    dp[new_mask] = new_cost;
    push(new_mask);
}

Recognition Guide

• Grid width <= 12 and height large: profile DP.
• n around 20 with graph constraints: subset DP or connected subset DP.
• n around 40: meet-in-the-middle.
• State includes "used items": bitmask DP or BFS over masks.

Practice Problems

• CSES - Counting Tilings profile DP classic domino tiling by row masks.
• CSES - Elevator Rides state compression optimize pair state per subset.
• LeetCode 698 - Partition to K Equal Sum Subsets memo masks prune by bucket remainder.
• LeetCode 847 - Shortest Path Visiting All Nodes BFS masks graph search over state compression.