Domino and Tromino Tiling
We are given a 2xn grid and we need to return number of ways to tile the grid using domino (2x1 shape) and tromino(L shape) tiles.
We have 6 different types of shapes that we can work with. The shapes are Tile1, Tile2, etc. henceforth be recognized as their corresponding tile.
Since we are only given a 2xn grid let our current position be denoted by index i, which denotes we are denotes that we are currently at the ith column of the grid. There are tiles that we cannot choose based on how things fit with the previous tiles.
Let's approach using a brute-force approach. We are given a 2xn grid and let the current position of the grid be denoted at index i. The current choices, however are limited by the previous choices. Here are the choices that result from the corresponding column. Tile 2 is placed in pairs.
1. The first choice is to place tile 1 and move to the corresponding column, i + 1.
2. In the second choice, tile must be placed in pairs to avoid the bottom row gap. Do this and move to i + 2 column.
3. IN this choice, tile 3 can be placed, but a gap remains in bottom row of next column. Place it and move to i + 2 column, but we need to fill the gap of i + 1 column.
4. In this, tile 4 can be placed but a gap remains in top row. Move on to column i + 2, but remember we need to fill i + 1.
Now let's see how to fill gaps. These are all of the possible cases where we can recursively fill in our grid. We have 2 cases: one where we do not have gaps, and one where we do have gaps.
Let's first go over the one where we have no previous gaps:
One thing to do is place the tile 1 and move to tile i + 1 with previous gap equals to false. Another thing we can do is to place the tiles 2 on top of each other. The other case we either place tile 3 and tile 4 and move to i + 2 with gap at i + 1 column for solving it. Consider both cases. (2 * solve(i + 2, previousGap = true)).
With previous gaps present, we will place tile 5 or 6 to fill up that previous gap, and we will move to i + 1 with no gaps. We will go to solve(i + 1, previousGap = true). Otherwise, we will place t2 and now we will be in next column with a Gap.
Here's the brute C++ force code for
Start to End:
class Solution {
public:
const int MOD = 1e9+7;
int numTilings(int n) {
return solve(0, n, false);
}
long solve(int i, int n, bool previousGap) {
if(i > n) return 0;
if(i == n) return !previousGap;
if(previousGap) {
return (solve(i + 1, n, false) + solve(i + 1, n, true) % MOD;
}
return (solve(i + 1, n, false) + solve(i + 2, n, false) + 2l * solve(i + 2, n, true)) % MOD;
}
};
There's just a base case and recursive step.
And End to Start:
class Solution {
public:
const int MOD = 1e9 + 7;
int numTilings(int n, bool previousGap = false) {
if(n < 0) {
return 0;
}
if(n == 0) {
return !previousGap;
}
if(previousGap) {
return(numTilings(n - 1) + numTilings(n - 1, true)) % MOD;
}
return(numTilings(n - 1) + numTilings(n - 2) + 2l * numTilings(n - 2, true)) % MOD;
}
};
The time complexity is O(3^n) since we are branching out a maximum 3 times each. The issue here is time limited exceeded, so we'll need a more efficient way to do this, maybe dynamic programming?
Drawing out the recursion tree would be very redundant and would take an absurd amount of time, so we don't need to calculate the same results over and over again. We will use dynamic programming and memoize the result using array dp. dp[i][0] denotes the number of ways to tile the grid at the ith column with no gap and dp[i][1] denotes the number of ways to tile the grid at the i+1th column. The rest is similar logic just with these different rules and we want the last tile to be without a gap so in dp[i][j] j needs to be 0. The following code ensues.
class Solution {
public:
const int MOD = 1e9 + 7;
int numTilings(int n) {
dp[i][0] = (dp[i-1][0] + dp[i-2][0] + 2l*dp[i-2][1]) % MOD;
dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % MOD;
}
return dp[n][0];
}
};
In conclusion, list each possibility of each square and then recursively call each square in order to add more possibilities based on this. Dynamic programming and memoization help to curb the length of this recursion.
Comments
Post a Comment