Domino and Tromino Tiling

LeetCode Q 790 - Domino and Tromino Tiling

We have two types of tiles: a 2x1 domino shape, and an “L” tromino shape. These shapes may be rotated.
XX <- domino XX <- "L" tromino X
Given N, how many ways are there to tile a 2 x N board? Return your answer 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:
Input: 3 ; Output: 5
Explanation:
The five different ways are listed below, different letters indicates different tiles:
XYZ XXZ XYY XXY XYY XYZ YYZ XZZ XYY XXY
Note: N will be in range [1, 1000].

Solution :

Solution 1: DP

1. State: f[i][j], i: until which col the floor is all covered; j: the tail states.

   • f[i][0]: there is no redundant tail at ith col. (1st row: i, 2nd row: i)
   • f[i][1]: there is one more tail at 1st row. (1st row: i + 1, 2nd row: i)
   • f[i][2]: there is one more tail at 1st row. (1st row: i, 2nd row: i + 1)

2. state transfer fuction:

   • f[i][0] = f[i-1][0] + f[i - 2][0] + f[i-2][1] + f[i-2][2];
     Put one type I vertically, or put two I types horizontally, or put L type (two directions)
   • f[i][1] = f[i-1][0] + f[i-1][2];
     Put a type I across the top row, or put an L-shape
   • f[i][2] = f[i-1][0] + f[i-1][1];
     Place a type I across the next line, or put an L type

3. boundary cases:
   f[0][0] = f[1][0] = f[1][1] = f[1][2] = 1

Caution: use long to avoid integer overflow

4. Optimization:
   Since f[i] is only depends on f[i-1] and f[i-2], we can use sliding array to optimize space complexity to O(1).

Time Complexity: O(n)
Space Complexity: O(3n)

Code:

private static final long MOD = 1000000007; 
public int numTilings(int N) {
	if (N <= 2) return N;

	long[][] f = new long[N+1][3];
	
	f[0][0] = f[1][0] = f[1][1] = f[1][2] = 1;

	for (int i = 2; i <= N; i++) {
		f[i][0] = (f[i-1][0] + f[i-2][0] + f[i-2][1] + f[i-2][2]) % MOD;
		f[i][1] = (f[i-1][0] + f[i-1][2]) % MOD;
		f[i][2] = (f[i-1][0] + f[i-1][1]) % MOD;
	}

	return (int)f[N][0];
}