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).
1#include <stdio.h>
2#define MOD 1000000007
3
4int numTilings(int n) {
5 if (n < 3) return n;
6 int dp[n + 1];
7 dp[0] = 1;
8 dp[1] = 1;
9 dp[2] = 2;
10 for (int i = 3; i <= n; i++) {
11 dp[i] = ((2 * dp[i - 1] % MOD) + dp[i - 3] % MOD) % MOD;
12 }
13 return dp[n];
14}
15
16int main() {
17 int n = 3;
18 printf("%d\n", numTilings(n));
19 return 0;
20}The above code uses dynamic programming to solve the problem, leveraging an array dp[] to keep track of ways to tile boards of increasing lengths.
Initial conditions are dp[0] = 1, dp[1] = 1, and dp[2] = 2. The recurrence relationship derives from placing tiles in ways that affect the size 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.