grid47 Exploring patterns and algorithms
Aug 20, 2024
6 min read
Solution to LeetCode 790: Domino and Tromino Tiling Problem
You are given a 2 x n grid and two types of tiles: a 2 x 1 domino and a tromino (which can be rotated). You must cover the grid entirely with these tiles. The task is to find the number of possible ways to tile the 2 x n board, modulo 10^9 + 7. Each tile must cover exactly two adjacent squares, and every square must be covered by a tile.
Problem
Approach
Steps
Complexity
Input: You are given a single integer n, representing the length of the grid.
Example: n = 4
Constraints:
• 1 <= n <= 1000
Output: Return the number of ways to tile the 2 x n grid, modulo 10^9 + 7.
Example: Output: 11
Constraints:
• The output should be returned as a single integer.
Goal: To find the number of ways to tile a 2 x n grid with dominos and trominos, use dynamic programming to compute the number of ways for each grid size up to n.
Steps:
• Initialize a dynamic programming array where dp[i] stores the number of ways to tile a 2 x i grid.
• Base cases: dp[1] = 1, dp[2] = 2, dp[3] = 5.
• For each i from 4 to n, calculate dp[i] as (2 * dp[i-1] + dp[i-3]) % mod.
• Return dp[n].
Goal: Ensure that the value of n is within the specified range, i.e., 1 <= n <= 1000.
Steps:
• The value of n is between 1 and 1000 inclusive.
Assumptions:
• The input n is always valid, and there are no constraints on the arrangement of the tiles other than that they must fill the grid completely.
• Input: Input: n = 3
• Explanation: The number of ways to tile a 2 x 3 grid is 5. The five different ways are achieved by combining 2 x 1 dominoes and 2 x 2 trominos in different configurations.
• Input: Input: n = 1
• Explanation: There is only one way to tile a 2 x 1 grid, using one 2 x 1 domino. Hence, the output is 1.
Approach: We can approach this problem using dynamic programming by building the solution iteratively from smaller subproblems.
Observations:
• The problem can be solved efficiently using dynamic programming, where the solution to a problem depends on solutions to smaller subproblems.
• The key observation is that the number of ways to tile a 2 x n grid can be computed using the number of ways to tile smaller grids, leveraging previously computed results.
Steps:
• Create a dynamic programming array dp where dp[i] represents the number of ways to tile a 2 x i grid.
• Set the base cases: dp[1] = 1, dp[2] = 2, dp[3] = 5.
• For each i from 4 to n, compute dp[i] as (2 * dp[i-1] + dp[i-3]) % 10^9 + 7.
• Return dp[n] as the result.
Empty Inputs:
• There are no empty inputs, as the input is guaranteed to be a positive integer.
Large Inputs:
• For large inputs up to n = 1000, the solution should efficiently compute the number of ways using dynamic programming.
Special Values:
• For n = 1 and n = 2, the number of ways to tile the grid is very small (1 and 2 respectively).
Constraints:
• Ensure that all calculations are done modulo 10^9 + 7 to avoid overflow.
intnumTilings(int n) {
int mod =1e9+7;
vector<longlong> v(10001, 0);
v[1] =1;
v[2] =2;
v[3] =5;
if(n <=3) return v[n];
for(int i =4; i <= n; i++) {
v[i] = (2* v[i-1] + v[i-3]);
v[i] %= mod;
}
return v[n];
}
1 : Function Definition
intnumTilings(int n) {
The function 'numTilings' is defined with a parameter 'n', representing the length of the grid.
2 : Modulo Definition
int mod =1e9+7;
This line defines the modulus 'mod' as 1e9 + 7 to prevent integer overflow and ensure the result is within manageable limits.
3 : Array Initialization
vector<longlong> v(10001, 0);
A vector 'v' of size 10001 is initialized with all values set to 0. This vector will store the number of ways to tile grids of different lengths.
4 : Base Cases
v[1] =1;
The base case: there is one way to tile a 2x1 grid (using a single vertical domino).
5 : Base Cases
v[2] =2;
The base case: there are two ways to tile a 2x2 grid (using two vertical dominoes or two horizontal dominoes).
6 : Base Cases
v[3] =5;
The base case: there are five ways to tile a 2x3 grid. This is derived from the problem constraints.
7 : Early Return for Small n
if(n <=3) return v[n];
If 'n' is less than or equal to 3, the function returns the precomputed result from the base cases.
8 : Dynamic Programming Loop
for(int i =4; i <= n; i++) {
A loop starts from 4 up to 'n' to calculate the number of ways to tile grids of size 2x4, 2x5, etc., using the recurrence relation.
9 : Recurrence Relation
v[i] = (2* v[i-1] + v[i-3]);
The number of ways to tile a 2x' i' grid is calculated using the recurrence relation: v[i] = 2 * v[i-1] + v[i-3]. This accounts for different ways of filling the grid using smaller grids.
10 : Modulo Operation
v[i] %= mod;
The result is taken modulo 1e9 + 7 to prevent overflow and ensure it fits within the constraints.
11 : Return Result
return v[n];
Finally, the function returns the precomputed result for a grid of size 2xN.
Best Case: O(n), where n is the length of the grid.
Average Case: O(n), since we calculate dp[i] for each i from 1 to n.
Worst Case: O(n), where n is the maximum value of 1000.
Description: The time complexity is linear, as we only need to compute the result for each value of i from 1 to n once.
Best Case: O(1), if the solution is optimized to use constant space.
Worst Case: O(n), where n is the size of the grid, since we store the number of ways to tile each grid size in the dynamic programming array.
Description: The space complexity is linear, as we store the result for each grid size up to n.
