Pattern Guide
Profile DP (Broken Profile)
"Count tilings column by column. State = which cells in current column are filled."
Profile DP (broken profile DP) counts the number of ways to tile a grid with dominoes or other pieces by processing cells one at a time. State = bitmask of which cells in the current "profile" (boundary) are already filled. Transition: for each cell, either place a piece extending right or down. O(2^m × n×m) for n×m grid. Used for: domino tiling, polyomino counting, circuit layout.
Problems you can solve with this pattern
3 problems · click any to start solving
// Count ways to tile n×m grid with 1×2 dominoes
// Process cells column by column, state = which cells in column are "pre-filled"
function countDominoTilings(n, m) {
const MOD = 1e9 + 7;
// dp[mask] = ways to reach this column with mask indicating pre-filled cells
let dp = new Array(1 << n).fill(0);
dp[0] = 1; // start: no cells pre-filled in first column
for (let col = 0; col < m; col++) {
// For each column, process rows top to bottom
// Use DFS/recursion to enumerate valid placements
const ndp = new Array(1 << n).fill(0);
function dfs(row, prevMask, curMask) {
if (row === n) { ndp[curMask] += dp[prevMask]; return; }
const filled = (prevMask >> row) & 1;
if (filled) {
// This cell is already filled by a horizontal domino from previous column
dfs(row + 1, prevMask, curMask);
} else {
// Option 1: place horizontal domino extending to next column
dfs(row + 1, prevMask, curMask | (1 << row));
// Option 2: place vertical domino (needs row+1 to also be empty)
if (row + 1 < n && !((prevMask >> (row + 1)) & 1)) {
dfs(row + 2, prevMask, curMask);
}
}
}
for (let mask = 0; mask < (1 << n); mask++) {
if (dp[mask]) dfs(0, mask, 0);
}
dp = ndp.map(v => v % MOD);
}
return dp[0]; // all cells filled, no cells pre-filled for next column
}Profile DP processes the grid cell by cell, left to right, top to bottom. State: bitmask of whether each cell in the current column is already filled (by a piece placed from the previous column). For each new cell: if already filled (bit=1), move to next cell. If not filled: either leave it for a vertical piece (try extending right and coming back) or place a horizontal piece (requires adjacent cell to the right is also free). Count ways to reach a fully filled state at the end.
// Count ways to tile n×m grid with 1×2 dominoes
// Process cells column by column, state = which cells in column are "pre-filled"
function countDominoTilings(n, m) {
const MOD = 1e9 + 7;
// dp[mask] = ways to reach this column with mask indicating pre-filled cells
let dp = new Array(1 << n).fill(0);
dp[0] = 1; // start: no cells pre-filled in first column
for (let col = 0; col < m; col++) {
// For each column, process rows top to bottom
// Use DFS/recursion to enumerate valid placements
const ndp = new Array(1 << n).fill(0);
function dfs(row, prevMask, curMask) {
if (row === n) { ndp[curMask] += dp[prevMask]; return; }
const filled = (prevMask >> row) & 1;
if (filled) {
// This cell is already filled by a horizontal domino from previous column
dfs(row + 1, prevMask, curMask);
} else {
// Option 1: place horizontal domino extending to next column
dfs(row + 1, prevMask, curMask | (1 << row));
// Option 2: place vertical domino (needs row+1 to also be empty)
if (row + 1 < n && !((prevMask >> (row + 1)) & 1)) {
dfs(row + 2, prevMask, curMask);
}
}
}
for (let mask = 0; mask < (1 << n); mask++) {
if (dp[mask]) dfs(0, mask, 0);
}
dp = ndp.map(v => v % MOD);
}
return dp[0]; // all cells filled, no cells pre-filled for next column
}1. Process cells left-to-right, top-to-bottom
2. State = bitmask of current column profile (which cells are pre-filled)
3. For each cell in each column: enumerate all valid placements
4. Transition to next state via DFS within a column
Complexity: O(2^m × n × m) for n×m grid with m ≤ row dimension
Tip: Orient the grid so m ≤ min(n,m) to minimize state space. For 4×n grids, 2^4 = 16 states; for 12×n, 2^12 = 4096 states (manageable).