505. Domino and Tromino Tiling
You have an endless supply of two tile shapes: a domino that covers two cells (a 2 × 1 rectangle, placeable vertically or horizontally) and an L-shaped tromino that covers three cells (rotatable into any of its four orientations).
Your function receives a single integer n. Return the number of different ways to tile a 2 × n board completely, modulo 10^9 + 7. Two tilings count as different if there is a pair of touching cells that one tile covers in the first tiling but two different tiles cover in the second.
Example 1:
Input: n = 3
Output: 5
Explanation: The 2 × 3 board has five tilings: three vertical dominoes; a vertical domino plus two horizontal ones (vertical on the left or on the right — two tilings); and two interlocking L-trominoes (two mirror arrangements).
Example 2:
Input: n = 1
Output: 1
Explanation: A 2 × 1 board fits exactly one vertical domino, and a tromino does not fit at all.
Constraints:
- 1 ≤ n ≤ 1000
- Answers are reported modulo 10⁹ + 7
Hints:
Try to build the board column by column and ask: what can the boundary between 'tiled so far' and 'still empty' look like? With these two tile shapes only two profiles are reachable — a flat edge, or an edge with one cell sticking out.
Track two quantities: f(i) = tilings of a full 2 × i board, and p(i) = coverings of a 2 × i board with one corner cell missing. Work out how a vertical domino, a pair of horizontal dominoes, and a tromino move you between these states: f(i) = f(i-1) + f(i-2) + 2·p(i-1) and p(i) = p(i-1) + f(i-2). Everything mod 10^9 + 7.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 3
Expected output: 5