790. 多米诺和托米诺平铺（难度：中等）

题目链接：https://leetcode.cn/problems/domino-and-tromino-tiling/

题目描述：

有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。

img

给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。

平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。

示例 1:

img

输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。

示例 2:

输入: n = 1
输出: 1

提示：

• 1 <= n <= 1000

解法：动态规划

考虑一种情况，在第i列之前的所有列都已经被瓷砖覆盖，在第i列以及之后都没有被覆盖。第i列从1开始，那么第i列有下面四种覆盖的方式：

• 一个方块都没有被覆盖，记为状态0；
• 上面方块被覆盖，记为状态1；
• 下面方块被覆盖，记为状态2；
• 两个方块都被覆盖，记为状态3。

使用 dp[i][j] 表示平铺到第i列时，各状态对应的方法数量。考虑第 i - 1 和第 i 列正方形，他们之间的状态转移图如下：（灰色表示已经铺好的，红色代码新铺的）

fig1

第0列，dp[0][0] = 0，dp[0][1] = 0，dp[0][2] = 0，dp[0][3] = 1，对应的状态转移方程（i>0）如下：

• dp[i][0] = dp[i-1][3]
• dp[i][1] = dp[i-1][3] + dp[i-1][2]
• dp[i][2] = dp[i-1][3] + dp[i-1][1]
• dp[i][3] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + + dp[i-1][3]

代码：

class Solution {
    static final int MOD = 1000000007;

    public int numTilings(int n) {
        int[][] dp = new int[n + 1][4];
        dp[0][3] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i - 1][3];
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
            dp[i][3] = (((dp[i - 1][0] + dp[i - 1][1]) % MOD + dp[i - 1][2]) % MOD + dp[i - 1][3]) % MOD;
        }
        return dp[n][3];
    }
}