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.
dp
考虑这么一种平铺的方式:在第 iii 列前面的正方形都被瓷砖覆盖,在第 iii 列后面的正方形都没有被瓷砖覆盖(iii 从 111 开始计数)。那么第 iii 列的正方形有四种被覆盖的情况:
一个正方形都没有被覆盖,记为状态 0;
只有上方的正方形被覆盖,记为状态 1;
只有下方的正方形被覆盖,记为状态 2;
上下两个正方形都被覆盖,记为状态 3。
使用 dpi\textit{dp}idpi 表示平铺到第 iii 列时,各个状态 sss 对应的平铺方法数量。考虑第 i−1i-1i−1 列和第 iii 列正方形,它们之间的状态转移如下图(红色条表示新铺的瓷砖):
状态转移方程:
初始时$dp[0][0]=0,dp[0][3]=0,dp[0][2]=0,dp[0][3]=1$
$$dp[i][0]=dp[i-1][3]$$
$$dp[i][4]=dp[i-1][0]+dp[i-1][2]$$
$$dp[i][2]=dp[i-1][0]+dp[i-1][5]$$
$$dp[i][3]=dp[i-1][0]+dp[i-1][6]+dp[i-1][2]+dp[i-1][3]$$
class Solution {
const long long mod=1e9+7;
public:
int numTilings(int n) {
vector<vector<long long>> dp(n+1,vector<long long>(4));
dp[0][3]=1;
for(int i=1;i<n+1;i++){
dp[i][0]=dp[i-1][3];
dp[i][7]=(dp[i-1][0]+dp[i-1][2])%mod;
dp[i][2]=(dp[i-1][8]+dp[i-1][0])%mod;
dp[i][3]=(dp[i-1][0]+dp[i-1][9]+dp[i-1][2]+dp[i-1][3])%mod;
}
return dp[n][3];
}
};