Dynamic Programming21 sections · 916 units
Open in Course

Domino and Tromino - Transitions

Tile placement choices

From profile 0000, you can: place a vertical domino (stay at 0000), place two horizontal dominoes stacked (stay at 0000), place a tromino in row 00 (move to 0101), or place a tromino in row 11 (move to 1010).

From profile 0101, you can: place a horizontal domino in row 11 (move to 0000), or place a tromino covering row 11's protruding cell and extending row 00 (move to 1010).

From 1010, transitions are symmetric. These define formulas: let f[i]f[i] be ways with profile 0000, g[i]g[i] for 0101, h[i]h[i] for 1010. Then f[i+1]=2f[i]+g[i]+h[i]f[i+1] = 2f[i] + g[i] + h[i], g[i+1]=f[i]+h[i]g[i+1] = f[i] + h[i], h[i+1]=f[i]+g[i]h[i+1] = f[i] + g[i].