Watch 10 video solutions for Domino and Tromino Tiling, a medium level problem involving Dynamic Programming. This walkthrough by WilliamFiset has 46,257 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.
Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 109 + 7.
In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.
Example 1:
Input: n = 3 Output: 5 Explanation: The five different ways are show above.
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 1000Problem Overview: Given a 2 x n board, count the number of ways to completely tile it using dominoes (2x1 or 1x2) and L-shaped trominoes. The challenge is handling partial shapes created by tromino placements and counting all valid tilings efficiently.
Approach 1: Dynamic Programming Recurrence (O(n) time, O(1) space)
This problem becomes manageable once you observe how the board grows from smaller widths. Let dp[i] represent the number of ways to tile a 2 x i board. Domino placements extend the board by one column, while tromino placements create configurations that connect across multiple columns. Careful enumeration of these transitions leads to the recurrence dp[i] = 2 * dp[i-1] + dp[i-3]. The intuition: one vertical domino extends dp[i-1], horizontal domino pairs or mirrored tromino shapes contribute additional combinations. Iterate from 1..n while storing only the last three states, reducing memory to constant space. This technique is a classic use of dynamic programming where each state builds directly from smaller solved subproblems.
Approach 2: Matrix Exponentiation (O(log n) time, O(1) space)
The recurrence dp[i] = 2*dp[i-1] + dp[i-3] is linear, which means it can be expressed as a matrix transition. By representing the state vector as [dp[i], dp[i-1], dp[i-2]], you can construct a fixed 3x3 transformation matrix that advances the sequence by one step. Raising this matrix to the (n-2) power using fast exponentiation computes the result in logarithmic time. Each multiplication combines previous tiling counts according to the recurrence relation. This approach relies on matrix exponentiation to accelerate linear recurrences and is useful when n becomes extremely large.
Recommended for interviews: The dynamic programming recurrence is what most interviewers expect. It demonstrates that you can analyze tile placements, derive a recurrence, and implement an efficient O(n) solution with constant memory. Matrix exponentiation is rarely required during interviews but shows deeper understanding of linear recurrences and optimization techniques often discussed in advanced dynamic programming problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming Recurrence | O(n) | O(1) | Standard solution for interview settings and typical constraints |
| Matrix Exponentiation | O(log n) | O(1) | Useful when n is extremely large and recurrence can be expressed as matrix transitions |