leetcode 790

问题

We have two types of tiles: a 2x1 domino shape, and an “L” tromino shape. These shapes may be rotated.

1
2
3
4
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.)

1
2
3
4
5
6
7
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].

分析

$dp[i]$ 表示填充完本列之后对下一列所产生的影响。$dp[0]$ 表示填充本列没有对下一行产生影响，$dp[1]$ 表示填充完本列导致下一列的第一行被占用，$dp[2]$ 表示填充完本列导致下一列的第二行被占用，$dp[3]$ 表示填充完本列导致下一列的两行都被占用。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numTilings(int N) {
        vector<int> dp(4, 0), dp2;
        dp[0] = 1;
        for (int i = 1; i <= N; ++i) {
            dp2 = dp;
            dp[0] = (dp2[0] + dp2[3])%1000000007;
            dp[1] = (dp2[0] + dp2[2])%1000000007;
            dp[2] = (dp2[0] + dp2[1])%1000000007;
            dp[3] = ((dp2[0] + dp2[1])%1000000007 + dp2[2])%1000000007;
        }
        return dp[0];
    }
};