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 <vector>
2using namespace std;
3
4class Solution {
5public:
6 int numTilings(int n) {
7 const int MOD = 1000000007;
8 if (n < 3) return n;
9 vector<int> dp(n + 1);
10 dp[0] = 1;
11 dp[1] = 1;
12 dp[2] = 2;
13 for (int i = 3; i <= n; i++) {
14 dp[i] = ((2LL * dp[i - 1] % MOD) + dp[i - 3] % MOD) % MOD;
15 }
16 return dp[n];
17 }
18};The C++ solution uses the vector to maintain the dynamic programming array. It captures the number of ways to cover increasingly larger sections of the board, using modulo arithmetic to prevent 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).
1class Solution:
2 def numTilings
Utilizing transform matrices, the Python solution applies fast matrix exponentiation to reduce computational cost, describing the recurrence relation succinctly with the transition matrix.