790. 多米诺和托米诺平铺

790. 多米诺和托米诺平铺

题解： dp

1. num数组表示的是：i-1列的瓷砖都被铺满了，第i列的状态枚举
2. 第i列的状态枚举有4种： 11 表示 上下两行都被填充， 10 表示上面那行被填充， 01 表示下面那行被填充， 00 表示两行都没有被填充
3. 转移方程： num[i+1][k] = num[i][k] + num[i][j] * w[j][k]
4. 数组从0开始，所以答案取 第n列的00 状态， 表示，从0 ~ n-1列都被铺好，且第n列两行都没有被填充

class Solution {
    int[][] num = new int[1005][4];
    int mod = (int) (1e9 + 7);
    public int numTilings(int n) {
        int[][] w = new int[][]{
                new int[]{1, 1, 1, 1},
                new int[]{0, 0, 1, 1},
                new int[]{0, 1, 0, 1},
                new int[]{1, 0, 0, 0}
        };
        num[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    num[i + 1][k] = (num[i + 1][k] + num[i][j] * w[j][k]) % mod;
                }
            }
        }
        return num[n][0];
    }
}