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 <= 1000The key idea in #790 Domino and Tromino Tiling is to count the number of ways to tile a 2 x n board using dominoes and L-shaped trominoes. A brute-force enumeration quickly becomes infeasible because the number of configurations grows exponentially. Instead, the problem is best solved using dynamic programming.
Define DP states that represent the number of valid tilings for boards of different lengths. Besides the fully covered board state, it is helpful to track a partially filled configuration caused by tromino placements. By analyzing how dominoes and trominoes extend from smaller boards, you can derive recurrence relations that build solutions for larger n from previously computed states.
The DP transitions reuse previously computed values, allowing the algorithm to run in linear time. With careful state compression, the space usage can also be reduced to constant memory. Since the result can grow large, computations are typically performed using a modulus such as 10^9 + 7.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with States | O(n) | O(n) |
| Optimized DP (State Compression) | O(n) | O(1) |
WilliamFiset
This problem can be solved using dynamic programming by considering the number of ways to tile smaller sections of the board and building up to solve for larger sections.
Define a DP array where dp[i] represents the number of ways to tile a 2 x i board.
The recurrence relation involves using domino and tromino tiles:
dp[i] = dp[i-1] + dp[i-2] + 2 * sum[dp[j-2] for j in 3 to i]This relation stems from the ways to construct tilings using the previous configurations.
Time Complexity: O(n).
Space Complexity: O(n).
1var numTilings = function(n) {
2 const MOD = 1000000007;
3 if (n < 3) return n;
4The JavaScript solution leverages a dynamic programming array dp to compute the solution, similar in design to the other solutions.
This solution uses matrix exponentiation to derive the result by considering the recurrence relation characteristic equation derived earlier. This approach is efficient for large n due to the optimization from reducing the problem to matrix multiplications.
Time Complexity: O(log n).
Space Complexity: O(1).
1public class Solution {
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Trominoes create temporary gaps or partial configurations that cannot be represented by a fully filled board state alone. Tracking these partial states ensures the DP transitions correctly count all valid tiling combinations.
Yes, variations of tiling and dynamic programming problems are common in FAANG-style interviews. This problem tests recurrence reasoning, state design, and optimization of DP solutions.
A dynamic programming array is typically used to store the number of tilings for smaller board sizes. In optimized versions, only a few previous states are required, allowing the DP array to be reduced to a few variables for constant space usage.
The optimal approach uses dynamic programming to build solutions for a 2 x n board from smaller board configurations. By tracking both fully filled and partially filled states created by tromino placements, you can derive recurrence relations and compute results efficiently in linear time.
The Matrix Exponentiation approach in Java employs transitioning matrices and the modular arithmetic for stability.