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).
1class Solution:
2 def numTilings(self, n: int) -> int:
3 MOD = 1000000007
4 if n < 3:
5 return n
6 dp = [0] * (n + 1)
7 dp[0], dp[1], dp[2] = 1, 1, 2
8 for i in range(3, n + 1):
9 dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD
10 return dp[n]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;
}
};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.