Formatted question description: https://leetcode.ca/all/790.html
790. Domino and Tromino Tiling
Level
Medium
Description
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 4directionally 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
Use dynamic programming. For N <= 2
, the results are straightforward. If N
equals 0 or 1, the result is 1 (note that when N
equals 0, no tile is needed, which counts for one way). If N
equals 2, the result is 2.
For N >= 3
, the board can be tiled by adding one vertical domino after N  1
columns, which counts for one way, or adding two horizontal dominoes after N  2
columns, which counts for one way, or adding two trominoes and several dominoes after N  k
columns where 3 <= k <= N
, which count for two ways for each k
.
Let f(N)
be the number of ways to tile a 2 x N board. It can be seen that f(0) = 1, f(1) = 1, f(2) = 2, and for N >= 3, f(N) = f(N  1) + f(N  2) + (f(0) + f(1) + … + f(N  3)) * 2. Apply the same recurrence formula for f(N  1), and it can be induced that for N >= 3, f(N) = f(N  1) * 2 + f(N  3). Apply this formula to obtain f(N).

class Solution { public int numTilings(int N) { if (N == 0) return 1; if (N <= 2) return N; final int MODULO = 1000000007; int prev2 = 1, prev1 = 1, cur = 2; for (int i = 3; i <= N; i++) { int next = (cur * 2 % MODULO + prev2) % MODULO; prev2 = prev1; prev1 = cur; cur = next; } return cur; } }

// OJ: https://leetcode.com/problems/dominoandtrominotiling/ // Time: O(N) // Space: O(N^2) class Solution { public: int numTilings(int n) { long mod = 1e9 + 7; vector<vector<long>> dp(n + 2, vector<long>(n + 2)); dp[1][1] = 1; for (int i = 2; i <= n + 1; ++i) { dp[i][i] = (dp[i  1][i  1] + dp[i  1][i  2] * 2 + dp[i  2][i  2]) % mod; dp[i][i  1] = (dp[i  1][i  2] + dp[i  2][i  2]) % mod; } return dp[n + 1][n + 1]; } };

class Solution: def numTilings(self, N): """ :type N: int :rtype: int """ dp = [[0] * 2 for _ in range(N + 1)] dp[0][0] = 1 dp[1][0] = 1 for i in range(2, N + 1): dp[i][0] = (dp[i  1][0] + dp[i  2][0] + 2 * dp[i  1][1]) % (10 ** 9 + 7) dp[i][1] = (dp[i  2][0] + dp[i  1][1]) % (10 ** 9 + 7) return dp[1][0]