Domino And Tromino Tiling Problem

Description

LeetCode Problem 790.

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.

Example 1:

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

Example 2:

``````1
2
Input: n = 1
Output: 1
``````

Constraints:

• 1 <= n <= 1000

Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
/* Using 1-indexed Levels:
dp1[i] denotes the number of ways with all cols from 1 to i filled
dp2[i] denotes the number of ways with all cols from 1 to i - 1 filled and only top grid in col i is filled
dp3[i] denotes the number of ways with all cols from 1 to i - 1 filled and only bottom grid in col i is filled

Base Cases:
dp1[1] = 1; dp1[2] = 2
dp2[1] = 0; dp2[2] = 1
dp3[1] = 0; dp3[2] = 1;

DP relation: (for all i >= 3)
dp1[i] = dp1[i - 1] (add 1 vertical domino) + dp1[i - 2] (add 2-horizontal dominoes)  + dp2[i - 1] (add 1 tromino in _| manner) + dp3[i - 1] (add 1 tromino such that top space in i - 1 col and i col gets filled)
dp2[i] = dp1[i - 2] (put one tribonaaci) + dp3[i - 1] (put on domino in horizontal fashion)
similarly => dp3[i] = dp1[i - 2] + dp2[i - 1]
*/
int numTilings(int n) {
if (n == 1)
return 1;

long long mod = 1e9+7;

vector<long long int> dp1(n + 1, 0);
vector<long long int> dp2(n + 1, 0);
vector<long long int> dp3(n + 1, 0);

dp1[1] = 1;
dp1[2] = 2;
dp2[1] = 0;
dp2[2] = 1;
dp3[1] = 0;
dp3[2] = 1;

for (int i = 3 ; i <= n ; i++) {
dp1[i] = (dp1[i - 1] + dp1[i - 2] + dp2[i - 1]+ dp3[i - 1]) % mod;
dp2[i] = (dp1[i - 2] + dp3[i - 1]) % mod;
dp3[i] = (dp1[i - 2] + dp2[i - 1]) % mod;
}

return dp1[n];
}
};
``````