Domino and Tromino Tiling
Medium · Dynamic Programming · Dynamic Programming
Problem
You have two kinds of tiles: a 2 x 1 domino and an L-shaped tromino that covers three cells. Either tile may be rotated.
Return the number of ways to tile a 2 x n board completely with these tiles. The number can be very large, so return it modulo 10^9 + 7.
Two tilings are different when some two neighboring cells are covered by the same tile in one tiling and by different tiles in the other.
Examples
Input: n = 2 Output: 2
Two vertical dominoes, or two horizontal dominoes stacked.
Input: n = 4 Output: 11
The counts for n = 1, 2, 3, 4 are 1, 2, 5, 11: each is 2 · f(n-1) + f(n-3).
Constraints
- 1 <= n <= 1000
Approaches
- Sum over the last unbreakable block — time O(n²), space O(n)
Follow-up
What if n could be 10^18? The recurrence f(n) = 2 f(n-1) + f(n-3) is linear, so the vector (f(n), f(n-1), f(n-2)) is a 3 x 3 matrix times the previous one. Raising that matrix to the n-th power by repeated squaring takes O(log n) multiplications.
Related problems
Start free on Cariara · Coding problems · System design studio
