Broken Profile DP

DP over a grid where the state is the boundary between the filled and unfilled regions. Used for tilings, connectivity constraints, and any grid problem where a cell’s validity depends on its neighbours.

Row-by-row profile DP

The simpler form: process one row at a time, with the state being a bitmask of which cells in the previous row are occupied or “stick out”.

$dp[\text{row}][\text{mask}]=\text{ways to fill rows }\mathrm{0..}\text{row}\text{ leaving profile }\text{mask}.$

Domino tiling of an $n\times m$ grid:

// mask bit j = 1 means cell (row, j) is already filled by a vertical domino from above
long long dominoTiling(int n, int m) {
    vector<long long> dp(1 << m, 0), ndp;
    dp[0] = 1;
    for (int r = 0; r < n; r++) {
        ndp.assign(1 << m, 0);
        for (int mask = 0; mask < (1 << m); mask++) {
            if (!dp[mask]) continue;
            fill(0, mask, 0, m, dp[mask], ndp);       // recursive filler below
        }
        dp = ndp;
    }
    return dp[0];
}
 
void fill(int col, int mask, int next, int m, long long ways, vector<long long>& ndp) {
    if (col == m) { ndp[next] += ways; return; }
    if (mask >> col & 1) { fill(col + 1, mask, next, m, ways, ndp); return; }  // occupied
    fill(col + 1, mask, next | (1 << col), m, ways, ndp);                      // vertical
    if (col + 1 < m && !(mask >> (col + 1) & 1))
        fill(col + 2, mask, next, m, ways, ndp);                               // horizontal
}

$O(n\cdot 2^m\cdot m)$ — so $m$ must be small (say $\le 15$). Always process along the shorter dimension.

True broken profile — cell by cell

Instead of a whole row at a time, advance one cell at a time. The state is the “staircase” boundary: $m$ bits describing the frontier, which crosses two adjacent rows.

This reduces the transition to $O(1)$ per state, giving $O(nm{2}^m)$ total with a much smaller constant, and it makes irregular constraints far easier to express.

// dp[mask] over cells in row-major order
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        ndp.assign(1 << m, 0);
        for (int mask = 0; mask < (1 << m); mask++) {
            if (!dp[mask]) continue;
            bool filled = mask >> j & 1;
            if (filled) ndp[mask ^ (1 << j)] += dp[mask];        // already covered
            else {
                if (i + 1 < n) ndp[mask | (1 << j)] += dp[mask]; // place vertical
                if (j + 1 < m && !(mask >> (j+1) & 1))
                    ndp[mask | (1 << (j+1))] += dp[mask];        // place horizontal
            }
        }
        dp = ndp;
    }

The bit for column $j$ means “cell $(i,j)$ is already covered by something placed earlier”.

Beyond tilings: connectivity profiles

Some grid problems need the profile to record not just occupancy but which frontier cells are connected to each other — for counting Hamiltonian circuits, connected regions, or plugin-style problems. The state becomes a minimum representation (a canonical labelling of the connectivity classes on the frontier), stored in a hash map because the state space is sparse.

This is the “plug DP” / “connection profile” technique. It is heavy machinery, but it is what makes problems like “count simple cycles covering every cell of a $12\times 12$ grid” tractable.

When to reach for it

Signal
Grid with one small dimension ($m\le 16$)	✔
Placing shapes that span cells (dominoes, L-trominoes, kings)	✔
Constraint between adjacent cells	✔
Counting tilings or configurations	✔
Both dimensions large	✘ — look for another structure
Constraint is global (connectivity of the whole board)	needs the connectivity-profile variant

Alternatives to check first

• Independent rows. If a row’s validity depends only on that row, it is a simple $O(n\cdot 2^m)$ DP with a precomputed compatibility table between consecutive masks.
• Matrix exponentiation. If the transition between row masks is a fixed matrix, matrix exponentiation handles $n$ up to $10^{18}$ in $O(8^m\log n)$.
• Closed forms. Domino tilings of $2\times n$ are Fibonacci; $3\times n$ satisfies a short linear recurrence. Compute small cases and check OEIS before writing profile DP.
• Matrix-Tree / permanents. Some tiling counts have determinant formulas (the Kasteleyn / FKT algorithm counts perfect matchings in planar graphs in polynomial time — including domino tilings of any planar region).

See also: Bitmask DP · Matrix Exponentiation · Designing States