2022.11.12 Domino and Tromino Tiling

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes. ![lc-domino.jpg][1] 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.

link

dp

考虑这么一种平铺的方式：在第 iii 列前面的正方形都被瓷砖覆盖，在第 iii 列后面的正方形都没有被瓷砖覆盖（iii 从 111 开始计数）。那么第 iii 列的正方形有四种被覆盖的情况： ![1.png][2] 一个正方形都没有被覆盖，记为状态 0；

只有上方的正方形被覆盖，记为状态 1；

只有下方的正方形被覆盖，记为状态 2；

上下两个正方形都被覆盖，记为状态 3。

使用 dp[i][s]\textit{dp}[i][s]dp[i][s] 表示平铺到第 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]

```c++ class Solution { const long long mod=1e9+7; public: int numTilings(int n) { vector<vector> dp(n+1,vector(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]; } };

  [1]: http://www.fengdaxian.xyz/usr/uploads/2022/11/3406384932.jpg
  [2]: http://www.fengdaxian.xyz/usr/uploads/2022/11/370693592.png
  [3]: http://www.fengdaxian.xyz/usr/uploads/2022/11/3406384932.jpg
  [4]: http://www.fengdaxian.xyz/usr/uploads/2022/11/3406384932.jpg
  [5]: http://www.fengdaxian.xyz/usr/uploads/2022/11/3406384932.jpg
  [6]: http://www.fengdaxian.xyz/usr/uploads/2022/11/3406384932.jpg
  [7]: http://www.fengdaxian.xyz/usr/uploads/2022/11/3406384932.jpg
  [8]: http://www.fengdaxian.xyz/usr/uploads/2022/11/3406384932.jpg
  [9]: http://www.fengdaxian.xyz/usr/uploads/2022/11/3406384932.jpg