Domino Tromino Tiling LeetCode 790

LeetCode 790 Domino and Tromino Tiling asks you to count the number of ways to tile a 2 x n board using two types of pieces: dominoes (2x1, placeable vertically or horizontally) and trominoes (L-shaped pieces that cover exactly 3 cells in an L configuration). The answer can be astronomically large, so you must return it modulo 10^9+7.

The 2 x n board has two rows and n columns. A vertical domino covers one full column. A horizontal domino covers one row across two adjacent columns. A tromino covers three cells in an L shape — it can appear in four rotations — and always leaves one cell of a column partially covered. Mixing trominoes with dominoes is what makes this problem harder than pure domino tiling.

For small values: ways(1)=1 (one vertical domino), ways(2)=2 (two vertical or two horizontal dominoes), ways(3)=5, ways(4)=11. The sequence grows rapidly, which is why modular arithmetic is mandatory. The problem guarantees 1<=n<=1000, so an O(n) iterative DP comfortably fits within limits.

To derive dp[n], consider how the rightmost column(s) of a fully tiled 2 x n board can be completed. If column n is filled by a single vertical domino, the remaining 2 x (n-1) board contributes dp[n-1] ways. If the last two columns are filled by two horizontal dominoes stacked on top of each other, that contributes dp[n-2] ways.

The tromino cases are trickier. A tromino placed at columns n-1 and n can leave a partial row protruding from column n-2. By carefully enumerating all four tromino rotations and the ways to complete the remaining board, you find that each tromino pair contributes dp[n-3] to the count (after accounting for symmetry between the top-protruding and bottom-protruding partial states). Summing all cases: dp[n] = dp[n-1] + dp[n-2] + 2*dp[n-3] + 2*dp[n-4] + ... which collapses via telescoping to dp[n] = 2*dp[n-1] + dp[n-3].

The final compact recurrence is dp[n] = 2*dp[n-1] + dp[n-3], with base cases dp[0]=1 (empty board), dp[1]=1, dp[2]=2. This single formula handles all tiling configurations — vertical dominoes, horizontal domino pairs, and tromino L-shapes — and can be computed iteratively in O(n) time with O(1) space by keeping only the last three dp values.

A rigorous derivation uses three states for each column boundary: F[n] (fully tiled up to column n), T[n] (fully tiled through column n-1, with the top cell of column n also covered — top-protruding), and B[n] (fully tiled through column n-1, with the bottom cell of column n also covered — bottom-protruding). Starting from these states you enumerate all valid piece placements.

The transition equations are: F[n] = F[n-1] (add vertical domino) + F[n-2] (add two horizontal dominoes) + T[n-1] (complete with tromino) + B[n-1] (complete with tromino); T[n] = F[n-2] (place tromino leaving top exposed) + B[n-1] (extend partial with horizontal domino); B[n] = F[n-2] (place tromino leaving bottom exposed) + T[n-1] (extend partial with horizontal domino). By symmetry T[n] = B[n] for all n.

Substituting T=B and simplifying: F[n] = F[n-1] + F[n-2] + 2*T[n-1]. Since T[n] = F[n-2] + T[n-1], you can express T[n-1] = F[n-3] + T[n-2] and continue unrolling. After telescoping the T terms, the combined recurrence reduces to dp[n] = 2*dp[n-1] + dp[n-3], confirming the compact formula without needing to maintain separate T and B arrays.

Pure domino tiling of a 2 x n board (with only 2x1 dominoes and no trominoes) follows the Fibonacci recurrence: dp[n] = dp[n-1] + dp[n-2]. Each column is either completed with one vertical domino (contributing dp[n-1]) or the last two columns are completed with two horizontal dominoes (contributing dp[n-2]). No partial states arise because dominoes always completely fill every column they touch.

Trominoes shatter this clean picture. An L-shaped tromino covers exactly 3 cells, which means it always spans parts of two columns and always leaves one cell of some column in a partial state. This partial state — one row of a column covered, the other not — requires a new state variable (T or B in the state machine). It is the coupling between these partial states that introduces the dp[n-3] term and breaks the simple Fibonacci structure.

The key difference is that Fibonacci DP only ever needs to look back 1 or 2 steps because dominoes tile in whole-column increments. The tromino forces a 3-step lookback because resolving a partial state created at column k requires filling columns k+1 and k+2 to return to a fully-tiled state, pushing the dependency out to dp[n-3]. Recognizing this distinction clarifies why the formula has a 3-step lookback even though each tromino only spans 2 columns.

The base cases for the recurrence dp[n] = 2*dp[n-1] + dp[n-3] are dp[0]=1 (the empty board has exactly one tiling — do nothing), dp[1]=1 (only one vertical domino fits), and dp[2]=2 (two vertical dominoes or two horizontal dominoes). You can verify dp[3]=5 manually: 2*dp[2]+dp[0] = 2*2+1 = 5, which matches the expected count of 5 tilings for a 2x3 board.

The modulus is 10^9+7 (one billion and seven), a well-known prime chosen because it is large enough that intermediate sums of two mod values do not overflow a 64-bit integer (since 2*(10^9+6) < 2^63-1), and small enough that modular inverses are easy to compute. Apply mod after every addition: dp[n] = (2*dp[n-1] + dp[n-3]) % MOD, not just at the final return.

When implementing with rolling variables, maintain three variables a, b, c representing dp[n-3], dp[n-2], dp[n-1] respectively. At each step compute next = (2*c + a) % MOD, then shift a=b, b=c, c=next. After n-2 iterations starting from n=3, c holds dp[n]. Remember to handle n=1 and n=2 as special cases that return before entering the loop.

Python iterative solution with rolling variables: def numTilings(n: int) -> int: MOD = 10**9 + 7; if n == 1: return 1; if n == 2: return 2; a, b, c = 1, 1, 2; for _ in range(3, n+1): a, b, c = b, c, (2*c + a) % MOD; return c. The tuple assignment evaluates the right-hand side atomically — (2*c + a) uses the old value of a before c overwrites it — giving correct rolling behavior in one line. Time O(n), space O(1).

Java iterative solution: public int numTilings(int n) { int MOD = 1_000_000_007; if (n == 1) return 1; if (n == 2) return 2; long a = 1, b = 1, c = 2; for (int i = 3; i <= n; i++) { long next = (2 * c % MOD + a) % MOD; a = b; b = c; c = next; } return (int) c; }. In Java use long for a, b, c, next to avoid integer overflow before the modulo — 2*c can reach 2*(10^9+6) which overflows int but fits in long. Cast back to int only at the return.

Both solutions run O(n) time and O(1) space. An alternative is to use an array dp[0..n] initialized with the base cases and filled iteratively, which is equivalent but uses O(n) space. The rolling-variable version is preferred in interviews because it demonstrates awareness of space optimization and avoids allocating a large array for the n=1000 case.

Climbing Stairs (LeetCode 70) is the simplest tiling problem: tile a 1 x n board with 1x1 and 1x2 pieces, giving the Fibonacci recurrence dp[n] = dp[n-1] + dp[n-2]. Tribonacci Number (LeetCode 1137) extends this to three-step lookback: dp[n] = dp[n-1] + dp[n-2] + dp[n-3]. Domino-Tromino Tiling is harder than both because the tromino introduces partial states that create the asymmetric 2*dp[n-1] + dp[n-3] shape rather than a simple sum of predecessors.

Decode Ways (LeetCode 91) is another DP problem with a similar two-step lookback but adds conditional logic: each step checks whether the single digit and the two-digit number are valid decode targets. The structural similarity — a rolling DP where each state depends on 1-2 prior states — makes it a good companion problem for building intuition about when and how to extend the lookback window.

The broader family of tiling DP problems — Domino-Tromino, Climbing Stairs, Tribonacci, Decode Ways — all share the pattern of deriving a recurrence by carefully enumerating how the rightmost position(s) can be completed. The key skill is drawing the state transitions explicitly before coding, especially when pieces can create partial states that span multiple columns.