Description#
You have two types of tiles: a 2 x 1
domino shape and a tromino shape. You may rotate these shapes.
![](https://spcdn.pages.dev/leetcode/problems/0790.Domino%20and%20Tromino%20Tiling/images/lc-domino.jpg)
Given an integer n, return the number of ways to tile an 2 x n
board. Since the answer may be very large, return it modulo 109 + 7
.
In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/0790.Domino%20and%20Tromino%20Tiling/images/lc-domino1.jpg)
Input: n = 3
Output: 5
Explanation: The five different ways are show above.
Example 2:
Input: n = 1
Output: 1
Constraints:
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution:
def numTilings(self, n: int) -> int:
@cache
def dfs(i, j):
if i > n or j > n:
return 0
if i == n and j == n:
return 1
ans = 0
if i == j:
ans = (
dfs(i + 2, j + 2)
+ dfs(i + 1, j + 1)
+ dfs(i + 2, j + 1)
+ dfs(i + 1, j + 2)
)
elif i > j:
ans = dfs(i, j + 2) + dfs(i + 1, j + 2)
else:
ans = dfs(i + 2, j) + dfs(i + 2, j + 1)
return ans % mod
mod = 10**9 + 7
return dfs(0, 0)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int numTilings(int n) {
long[] f = {1, 0, 0, 0};
int mod = (int) 1e9 + 7;
for (int i = 1; i <= n; ++i) {
long[] g = new long[4];
g[0] = (f[0] + f[1] + f[2] + f[3]) % mod;
g[1] = (f[2] + f[3]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[0];
f = g;
}
return (int) f[0];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
const int mod = 1e9 + 7;
int numTilings(int n) {
long f[4] = {1, 0, 0, 0};
for (int i = 1; i <= n; ++i) {
long g[4] = {0, 0, 0, 0};
g[0] = (f[0] + f[1] + f[2] + f[3]) % mod;
g[1] = (f[2] + f[3]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[0];
memcpy(f, g, sizeof(g));
}
return f[0];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func numTilings(n int) int {
f := [4]int{}
f[0] = 1
const mod int = 1e9 + 7
for i := 1; i <= n; i++ {
g := [4]int{}
g[0] = (f[0] + f[1] + f[2] + f[3]) % mod
g[1] = (f[2] + f[3]) % mod
g[2] = (f[1] + f[3]) % mod
g[3] = f[0]
f = g
}
return f[0]
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def numTilings(self, n: int) -> int:
f = [1, 0, 0, 0]
mod = 10**9 + 7
for i in range(1, n + 1):
g = [0] * 4
g[0] = (f[0] + f[1] + f[2] + f[3]) % mod
g[1] = (f[2] + f[3]) % mod
g[2] = (f[1] + f[3]) % mod
g[3] = f[0]
f = g
return f[0]
|