Skip to content

790. Domino and Tromino Tiling

Description

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

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:

Input: n = 3
Output: 5
Explanation: The five different ways are show above.

Example 2:

Input: n = 1
Output: 1

 

Constraints:

  • 1 <= n <= 1000

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]

Comments