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.
2022.11.12 Domino and Tromino Tiling
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 列的正方形有四种被覆盖的情况:
2022.11.12 Domino and Tromino Tiling

一个正方形都没有被覆盖,记为状态 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];
    }
};

评论区 0 已关闭评论