Domino and Tromino Tiling
Domino and Tromino Tiling: count the ways to fully tile a 2×n board using 2×1 dominoes and L-shaped trominoes, modulo 10⁹+7.
- 1 <= n <= 1000
- Return the answer modulo 10⁹ + 7.
Intuition
Trominoes leave a ragged edge, so counting only fully-filled columns is not enough. Track two states: full[i], the tilings whose first i columns are completely filled, and part[i], those with one protruding square. The recurrences then close on each other.
When a tiling piece leaves a ragged boundary, one DP state is never enough — add a state per distinct boundary shape. The tell is any piece that does not align to the grid's natural cut. Recognising that you need two interlocking recurrences is the whole insight, and the same reasoning generalises to broken-profile DP.
Approach
Before reading on: place a single tromino at the left edge of a 2×n board and look at the boundary it leaves. Can any state that only counts 'filled columns' describe it? Aim for O(n).
Why one state is not enough
For dominoes alone the count would satisfy f(n) = f(n-1) + f(n-2) — the Fibonacci recurrence — because every placement leaves a clean edge. Trominoes break that: placing one leaves a single square jutting into the next column, a configuration no purely-column-based state can express. Missing this is why naive attempts undercount from n = 3 onwards, and it is the entire difficulty of the problem.
The two recurrences
full[i] = full[i-1] + full[i-2] + 2 * part[i-1]. The first term is a vertical domino added to a filled edge; the second is two horizontal dominoes; the third closes a partial state from the previous column, which a tromino can complete in two mirror-image orientations — hence the factor of 2. Meanwhile part[i] = part[i-1] + full[i-2]: either extend an existing protrusion with a horizontal domino, or create a new one from a filled edge two columns back using a tromino. Note the asymmetry in the indices — part[i-1] in one and full[i-2] in the other — which is exactly where this recurrence is usually got wrong.
Base cases and the modulus
Seed full[1] = 1 (a single vertical domino), full[2] = 2 (two vertical or two horizontal), and part[2] = 1 — the first column where a protrusion can exist at all. Anything below that is zero, since a tromino needs two columns to leave a ragged edge. Take the modulus at every addition rather than only at the end, or the values overflow long before n reaches 1000. Iterating to n is O(n) time and, since only the previous two entries are ever read, O(1) space with rolling variables.
Solution & live demo
Common pitfalls
Using the Fibonacci recurrence alone
full[i] = full[i-1] + full[i-2]
full[i] = full[i-1] + full[i-2] + 2 * part[i-1]
That counts domino-only tilings. It gives 3 for n = 3 where the true answer is 5, because the two tromino arrangements are never counted.
Dropping the factor of two
full[i] = full[i-1] + full[i-2] + part[i-1]
... + 2 * part[i-1]
A partial state can be completed by a tromino in two mirror orientations — protruding from the top row or the bottom. Counting one halves every contribution from trominoes.
Applying the modulus only at the end
return full[n] % MOD
full[i] = (...) % MOD # inside the loop
The counts grow exponentially and blow past 64-bit range well before n = 1000, so the intermediate values are already wrong by the time the final modulus is taken.
Edge cases
Only a vertical domino fits, so the answer is 1.
Two vertical or two horizontal dominoes give 2.
The answer is 5 — the first case where trominoes matter, since dominoes alone would give 3.
Values exceed 64-bit range quickly, so the modulus must be applied inside the loop.
Never reached: the n <= 2 guard returns before the table is used.