Dare2Solve
The problem involves finding the number of ways to tile a 2xN board using a combination of dominoes (2x1 or 1x2 tiles) and trominoes (an "L" shape covering a 2x2 area minus one 1x1 square). Given an integer n
, you need to compute how many different ways you can completely cover a 2xN board.
The problem can be approached using dynamic programming by considering the different ways to fill the last column or set of columns. We start by understanding the base cases and then extend the logic for larger boards by considering the different possible tiles that can cover the last few squares of the board.
Base Cases:
n = 1
, there's only one way to cover the board with a vertical domino.n = 2
, there are two ways: two vertical dominoes or two horizontal dominoes.n = 3
, there are five ways: combinations of dominoes and a tromino.Dynamic Programming Transition:
n
, the number of ways to tile the board is determined by combining the solutions of smaller boards. The recurrence relation considers:
2 * dp[i - 1]
: This accounts for extending the board from a previously solved state using either a domino or a tromino.dp[i - 3]
: This accounts for using a tromino or a combination of dominoes to reach the current state.Implementation:
dp
array.dp
array up to the given n
.O(n)
because we iterate from 4 to n
to fill out the dp
array.
O(n)
because we store the number of ways to tile boards of size 0
to n
in the dp
array.
class Solution {
public:
int numTilings(int n) {
int mod = 1e9 + 7;
if (n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 5;
vector<long long> dp(n + 1);
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
dp[3] = 5;
for (int i = 4; i <= n; i++) {
dp[i] = (2 * dp[i - 1] + dp[i - 3]) % mod;
}
return dp[n];
}
};
class Solution:
def numTilings(self, n: int) -> int:
mod = 10**9 + 7
if n == 1:
return 1
if n == 2:
return 2
if n == 3:
return 5
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
dp[2] = 2
dp[3] = 5
for i in range(4, n + 1):
dp[i] = (2 * dp[i - 1] + dp[i - 3]) % mod
return dp[n]
class Solution {
public int numTilings(int n) {
int mod = 1000000007;
if (n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 5;
long[] dp = new long[n + 1];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
dp[3] = 5;
for (int i = 4; i <= n; i++) {
dp[i] = (2 * dp[i - 1] + dp[i - 3]) % mod;
}
return (int) dp[n];
}
}
var numTilings = function (n) {
let mod = 10 ** 9 + 7;
let len = 4;
let ways = new Array(len).fill(0);
ways[0] = 1;
ways[1] = 1;
ways[2] = 2;
if (n < len - 1) {
return ways[n];
}
for (var i = len - 1; i <= n; i++) {
ways[i % len] = (
ways[(len + i - 1) % len] * 2
+
ways[(len + i - 3) % len]
) % mod;
}
return ways[(i - 1) % len];
};