Profile DP — Broken-Profile Domino Tiling

Sweep an n×m grid cell by cell. Carry an m-bit frontier mask. At each free cell: place vertical (set the bit below), place horizontal (consume the right cell), or skip a filled cell. Cost O(n·m·2m).

step 0

Grid sweep (cell (0,0))

The frontier is the m-cell staircase between decided and undecided cells. Bit c of the mask = "frontier cell in column c already covered".
free filled (bit=1) current cell vertical horizontal

Frontier mask (m bits)

Transition at current cell

Running tiling count (this board):
—
Press Step to begin. We sweep cells in reading order, carrying the frontier mask, and at each free cell we branch into place-vertical / place-horizontal.
Self-contained visualization. Counting semiring (+,×); the panel shows one decision path through the broken-profile DP and, separately, the exact total number of tilings of the chosen board (computed by the full sweep). The answer of the full DP is dp[mask=0] after all n·m cells. See junior.md and professional.md for the proof that each decision appends one piece and the bijection between tilings and decision paths.