Dynamic Programming21 sections · 916 units
Open in Course

Domino and Tromino - Profile States

Three profile types

For 22 rows, the profile between columns can be: 0000 (both rows end at the same column), 0101 (row 00 ends earlier, row 11 sticks out), or 1010 (row 11 ends earlier, row 00 sticks out).

That's 33 states per column. State 0000 means both rows are flush. From here, you can place a vertical domino, two horizontal dominoes, or a tromino (which creates an uneven profile). State 0101 means row 11 has a protruding cell you must cover. You can place a tromino to fill it and make the profile 1010, or place a horizontal domino in row 11 to bring it flush to 0000.