Sign in to watch this lesson
Advanced - Dynamic Programming · 4:01
Broken-Profile DP: the "Parquet" Problem
To count the domino tilings of a board, we sweep it column by column and remember only a bitmask profile: which cells just past the frontier are already covered by dominoes poking across it. Filling each column from top to bottom gives the transitions, the table dp[column][mask] counts the 11 tilings of a 3 × 4 board, and moving the frontier one cell at a time (the broken profile) brings the work down to n·m·2ᵐ.
You will learn
- Define the profile state dp[column][mask], where bit r says that row r of the next column is already covered, and read the answer as dp[n][0]
- Generate the transitions by filling a column from top to bottom: skip a covered cell, lay a horizontal domino (setting the next column's bit) or stand a vertical one
- Replace the column-at-a-time pairs of masks (n·4ᵐ) by the cell-by-cell broken profile (n·m·2ᵐ), keeping the narrow side in the mask
- Handle the practical details: odd area gives 0, transpose when needed, work modulo a prime, and treat blocked cells as pre-covered