Dynamic Programming21 sections · 916 units
Open in Course

The Profile Concept

Column boundary states

When filling a grid column by column with tiles, some cells extend into the next column while others don't. The "profile" is which cells in the current column remain unfilled and stick out. For a column of height nn, there are 2n2^n possible profiles.

Each profile is a bitmask: bit ii set means row ii has a cell protruding from the previous column that you must account for. This profile tells you which cells are already occupied when you start filling the next column. Without tracking this, you can't know where tiles can legally go.