790. Domino and Tromino Tiling

1. 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 10$^9$ + 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.

2. Example

Example 1

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

Example 2

Input: n = 1
Output: 1

3. Constraints

• 1 <= n <= 1000

4. Solutions

Dynamic Programming

Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int numTilings(int n) {
        const int mod = 1e9 + 7;
        array<array<int, 4>, 2> tiles{{0, 0, 0, 1}};
        for (int i = 0; i < n; ++i) {
            tiles[1][0] = tiles[0][3];
            tiles[1][1] = (tiles[0][0] + tiles[0][2]) % mod;
            tiles[1][2] = (tiles[0][0] + tiles[0][1]) % mod;
            tiles[1][3] = ((long long)tiles[0][0] + tiles[0][1] + tiles[0][2] + tiles[0][3]) % mod;

            tiles[0] = tiles[1];
        }

        return tiles[0][3];
    }
};