多米诺和托米诺平铺【LC790】

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 109 + 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.

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

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

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

又是没做过的题型

• 思路：使用状态机DP，定义第i列瓷砖的四种不同状态【未铺满】，第i列瓷砖的状态可由前一列的瓷砖状态得到，最终dp[i][1]即为前i列瓷砖被铺满的方案数

。j=0时，代表第i列未被填充

。j=1时，代表第i列两个方块均被填充

。j=2时，代表第i列上面的方块被填充

。j=3时，代表第i列下面的方块被填充

动态规划实现

1.确定dp数组（dp table）以及下标的含义

dp[i][j]:当前i-1列铺满时，当前第i列状态为j时的方案数

j的取值范围为[0,4)

。j=0时，代表第i列未被填充

。j=1时，代表第i列两个方块均被填充

。j=2时，代表第i列上面的方块被填充

。j=3时，代表第i列下面的方块被填充

2.确定递推公式

。dp[i][0]：前i-1列被填充满，第i列未被填充

• 只能由dp[i-1][1]转移：在第i-1列竖放2*1的骨牌

dp[i][0] = dp[i-1][0]

。dp[i][1]：前i列均被填充

• 由dp[i-1][0]转移：在第i-1列和第i列横放1*2的骨牌

• 由dp[i-1][1]转移：在第i-1列和第i列竖放2*1的骨牌

• 由dp[i-1][2]转移：横放一块L型骨牌

• 由dp[i-1][3]转移：横放一块L型骨牌

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

。dp[i][2]：前i-1列被填充满、第i列上面的方块被填充

• 由dp[i-1][0]转移：横放一块L型骨牌

• 由dp[i-1][3]转移：横放一块L型骨牌

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

。dp[i][3]：前i-1列被填充满、第i列下面的方块被填充

• 由dp[i-1][0]转移：横放一块L型骨牌

• 由dp[i-1][2]转移：横放一块L型骨牌

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

3.dp数组如何初始化

dp[1][0]=1
dp[1][1]=1
dp[1][2]=0
dp[1][3]=0

4.确定遍历顺序

。正序遍历i

5.举例推导dp数组

• 代码

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

。复杂度

• 时间复杂度：O ( n )

• 空间复杂度：O ( n )

• 滚动数组优化

。int a = i & 1

奇数1 偶数0，确定下标

。int b = (i - 1) & 1

奇数0 偶数1

class Solution {
    public int numTilings(int n) {
        int MOD = (int)1e9 + 7;
        int[][] dp = new int[2][4];
        dp[1][0] = 1;
        dp[1][1] = 1;
        for (int i = 2; i <= n; i++){
            int a = i & 1;// 奇数1 偶数0
            int b = (i-1) & 1;// 奇数0 偶数1
            dp[a][0] = dp[b][1];
            int cur = 0;
            for (int j = 0; j < 4; j++){
                cur = (cur + dp[b][j]) % MOD;
            }
            dp[a][1] = cur;
            dp[a][2] = (dp[b][0] + dp[b][3]) % MOD;
            dp[a][3] = (dp[b][0] + dp[b][2]) % MOD;
        }
        return dp[n & 1][1];
    }
}

。复杂度

• 时间复杂度：O ( n )

• 空间复杂度：O ( 1 )