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 const 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}The C# solution implements the same dynamic programming strategy in an array dp, looping to compute tiling possibilities.
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).
1public class Solution {
2 final
The Matrix Exponentiation approach in Java employs transitioning matrices and the modular arithmetic for stability.