Sponsored
Sponsored
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).
1public class Solution {
2 public int numTilings(int n) {
3 final int MOD = 1000000007;
4 if (n < 3) return n;
5 int[] dp = new int[n + 1];
6 dp[0] = 1;
7 dp[1] = 1;
8 dp[2] = 2;
9 for (int i = 3; i <= n; i++) {
10 dp[i] = (2 * dp[i - 1] % MOD + dp[i - 3] % MOD) % MOD;
11 }
12 return dp[n];
13 }
14}In Java, the dynamic programming approach is similar to C/C++ implementations. The array dp stores ways to tile subproblems up to size n. The modulo operator prevents integer overflow.
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;
}
};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.