vii. Broken Profile DP

DP over a grid with one small dimension $m$ (up to 10–20), where the state is the boundary between processed and unprocessed cells. Three levels:

1. Row by row with a mask per row (compatibility between consecutive rows).
2. Cell by cell (“broken profile”): the frontier is a staircase of $m$ bits; $O(1)$ transitions, $O(nm{2}^m)$.
3. Plug DP (connectivity profile): the frontier also records which plugs are connected, for paths, cycles, and connected regions; states kept in a hash map.

Always put the small dimension in the profile. For huge $n$ with fixed $m$, the row transition is a fixed matrix: matrix power or Berlekamp–Massey on the first terms (Matrix Power DP).

Row by row

When a row’s choice interacts only with the previous row (no two adjacent kings/plants, non-attacking pieces in a strip), precompute valid row masks and compatible pairs:

vector<int> valid;                                        // masks with no two adjacent bits, fitting the row
for (int s = 0; s < 1 << m; s++) if (!(s & s >> 1) && (s & bad[row]) == 0) valid.push_back(s);
// dp[row][s] = sum over t in valid(row - 1) with (s & t) == 0 of dp[row - 1][t]

Number of masks without adjacent bits is $F_{m+2}$, so $m=20$ leaves only 17711 masks.

Cell by cell (domino tilings)

Process cells in row-major order. Bit $j$ of the mask says whether cell $(i,j)$ is already covered by a piece placed earlier (from the row above). At cell $(i,j)$:

• if covered: clear the bit (it now refers to cell $(i+1,j)$, which is free);
• else place a vertical domino (set bit $j$: covers $(i+1,j)$) or a horizontal one (requires bit $j+1$ clear, sets it).

ll dominoTilings(int n, int m) {                          // n x m board, m small
    vector<ll> dp(1 << m), nd(1 << m); dp[0] = 1;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        fill(all(nd), 0);
        for (int s = 0; s < 1 << m; s++) if (dp[s]) {
            if (s >> j & 1) { nd[s ^ 1 << j] += dp[s]; continue; }
            if (i + 1 < n) nd[s | 1 << j] += dp[s];
            if (j + 1 < m && !(s >> (j + 1) & 1)) nd[s | 1 << (j + 1)] += dp[s];
        }
        swap(dp, nd);
    }
    return dp[0];
}

Proof: the mask is a complete state

Invariant before cell $(i,j)$: bits $\mathrm{0..}j-1$ describe cells $(i+1,\mathrm{0..}j-1)$ and bits $j..m-1$ describe cells $(i,j..m-1)$, each saying whether the cell is already covered by a placed domino. Everything above the frontier is fully covered, and dominoes only reach one row/column ahead, so no other information about the past can affect which completions exist. Each transition covers cell $(i,j)$ in exactly one way (already covered, vertical, or horizontal), so each tiling corresponds to exactly one path of transitions, and the final state 0 means nothing sticks out of the board.

Plug DP: connectivity on the frontier

For Hamiltonian cycles/paths on grids, counting simple cycles, or “connected region” constraints, each frontier edge (plug) records whether a path crosses it and which other plug it is connected to. Two encodings:

• Bracket encoding (paths only, no branching): planarity makes the connected plug pairs nested, so label each plug 0 (none), 1 (left end, ”(”), 2 (right end, ”)”). 2 bits per plug.
• Minimum representation (connected components, possibly branching): label plugs by component number, renumbered in order of first appearance. 3–4 bits per plug.

There are $m+1$ plugs: $m$ vertical edges below the processed cells plus the horizontal edge entering the current cell. States are sparse, so store them in a hash map per cell.

ll hamiltonianCycles(const vector<string>& g) {           // '.' free, anything else blocked
    int n = sz(g), m = sz(g[0]), ei = -1, ej = -1;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (g[i][j] == '.') ei = i, ej = j;
    if (ei < 0) return 0;
    auto get = [](ull s, int p) { return int(s >> (2 * p) & 3); };
    auto put = [](ull s, int p, ull v) { return (s & ~(3ULL << (2 * p))) | (v << (2 * p)); };
    auto ok = [&](int i, int j) { return i < n && j < m && g[i][j] == '.'; };
    unordered_map<ull, ll> cur{{0, 1}}, nxt; ll ans = 0;
    for (int i = 0; i < n; i++) {
        nxt.clear(); for (auto [s, c] : cur) nxt[s << 2] += c; swap(cur, nxt);   // new row
        for (int j = 0; j < m; j++) {
            nxt.clear();
            for (auto [s, c] : cur) {
                int L = get(s, j), U = get(s, j + 1);            // plug from the left, plug from above
                if (g[i][j] != '.') { if (!L && !U) nxt[s] += c; continue; }
                if (!L && !U) { if (ok(i + 1, j) && ok(i, j + 1)) nxt[put(put(s, j, 1), j + 1, 2)] += c; }
                else if (!L || !U) {
                    int x = L | U;
                    if (ok(i + 1, j)) nxt[put(put(s, j, x), j + 1, 0)] += c;   // continue down
                    if (ok(i, j + 1)) nxt[put(put(s, j, 0), j + 1, x)] += c;   // continue right
                } else {
                    ull t = put(put(s, j, 0), j + 1, 0);
                    if (L == 1 && U == 1) {                      // the ")" matching U becomes "("
                        for (int k = j + 1, b = 0;; k++) { int v = get(s, k); b += v == 1 ? 1 : v == 2 ? -1 : 0; if (!b) { t = put(t, k, 1); break; } }
                        nxt[t] += c;
                    } else if (L == 2 && U == 2) {               // the "(" matching L becomes ")"
                        for (int k = j, b = 0;; k--) { int v = get(s, k); b += v == 2 ? 1 : v == 1 ? -1 : 0; if (!b) { t = put(t, k, 2); break; } }
                        nxt[t] += c;
                    } else if (L == 2 && U == 1) nxt[t] += c;    // join two paths
                    else if (i == ei && j == ej && t == 0) ans += c;   // L == 1, U == 2: close the cycle
                }
            }
            swap(cur, nxt);
        }
    }
    return ans;
}

(URAL 1519 “Formula 1”: $12\times 12$ grid with obstacles.) For Hamiltonian paths, add a third plug type “single end” and allow at most two of them; for “longest simple cycle” or weighted versions, store max instead of sum; for connected-region problems (“choose a connected set of cells maximising the sum”), use the minimum representation with an “in the region” bit per cell.

Proof: the bracket encoding is valid and the transitions are complete

The partial solution above the frontier is a set of vertex-disjoint paths (no cycle may close early, except the final one). Each path has both ends on the frontier. Because the processed region is simply connected and paths don’t cross, if path ends are at frontier positions $a<b$ and $c<d$ then the intervals $[a,b]$ and $[c,d]$ are nested or disjoint, exactly like matched parentheses; hence labelling left ends ”(” and right ends ”)” determines the pairing. At a free cell the path must enter and leave through exactly two of its four sides. With no incoming plugs, it must use down and right (a new path, ”(” then ”)”). With one incoming plug, the path continues down or right, keeping its label. With two incoming plugs, they are joined: ”((” merges two paths, and the partner of the second ”(” (its ”)”) becomes the ”(” of the merged path; ”))” symmetrically; ”)(” joins a path ending here from the left with one starting here, and their outer ends already have the correct labels; ”()” are the two ends of the same path, which closes a cycle, allowed only at the last free cell with no other plugs. These cases are exhaustive, so each Hamiltonian cycle corresponds to exactly one sequence of transitions.

Variants and tricks

• Obstacles, irregular boards: just skip transitions at blocked cells (as above).
• Counting tilings with several shapes (L-trominoes, $1\times 3$): profile per cell with bits for the next one or two rows.
• Placing pieces with longer-range attacks (queens are hopeless; knights need two previous rows): profile of the last two rows, $4^m$ states or less after pruning.
• Huge $n$: build the $2^m\times 2^m$ row-transition matrix and raise it to the $n$-th power, $O(8^m\log n)$; or compute $2^m$ + a few terms and use Berlekamp–Massey.
• Exact count of domino tilings for large boards: Kasteleyn’s determinant (Determinants) — more generally, the FKT algorithm counts perfect matchings (hence domino tilings) of any planar graph in polynomial time, not just grids.
• Check for a closed form before writing any profile DP: domino tilings of a $2\times n$ strip are Fibonacci numbers; $3\times n$ satisfies a short linear recurrence. Compute the first few small cases by brute force and check OEIS — a surprising fraction of “tiling count” problems have a known closed form or short recurrence, making the whole profile-DP machinery unnecessary.

When to reach for this

Signal
grid with one small dimension ($m\lesssim 16$)	use it
placing shapes that span cells (dominoes, L-trominoes, kings)	use it
constraint between adjacent cells only	use it
counting tilings or configurations	use it
both dimensions large	look for another structure — this doesn’t scale
constraint is global (connectivity of the whole board)	needs the connectivity-profile (plug DP) variant specifically