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).
1class Solution:
2 def numTilings(self, n: int) -> int:
3 MOD = 1000000007
4 if n < 3:This Python solution uses a list dp to implement the dynamic programming approach, iterating to compute the number of ways to place tiles for each board size from 1 to n.
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).
1#include <vector>
2using namespace std;
3
4const int MOD = 1000000007;
5
class Solution {
vector<vector<long long>> multiply(vector<vector<long long>>& A, vector<vector<long long>>& B) {
vector<vector<long long>> C(3, vector<long long>(3));
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
for (int k = 0; k < 3; ++k)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
}
vector<vector<long long>> matrixExponentiation(vector<vector<long long>>& A, int n) {
vector<vector<long long>> result = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; // Identity matrix
while (n) {
if (n % 2 == 1) result = multiply(result, A);
A = multiply(A, A);
n /= 2;
}
return result;
}
public:
int numTilings(int n) {
if (n < 3) return n;
vector<vector<long long>> T = {{0, 1, 0}, {1, 1, 1}, {0, 1, 0}};
vector<vector<long long>> res = matrixExponentiation(T, n-2);
return ((1LL * res[1][0] + res[1][1] * 2 + res[1][2]) % MOD) % MOD;
}
};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 arranges the problem in terms of a transform matrix based on the transition relations derived from examining the problem.
The matrix is exponentiated using fast exponentiation (squaring technique) to efficiently compute powers.