LeetCode790多米诺和托米诺平铺

题目描述

  有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 “L” 的托米诺形。两种形状都可以旋转。给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。

解析

  题目最后一句翻译成人话就是用这两种瓷砖要铺满且不能有重合。动态规划，对当前的位置分成四种情况：上下两个都是空，上空，下空和都是满的。

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];
    }
}

  由于上面的过程可以写成矩阵乘法，可以用快速幂来计算。

class Solution {
    static final int MOD = 1000000007;

    public int numTilings(int n) {
        int[][] mat = {
            {0, 0, 0, 1},
            {1, 0, 1, 0},
            {1, 1, 0, 0},
            {1, 1, 1, 1}
        };
        int[][] matn = {
            {1, 0, 0, 0},
            {0, 1, 0, 0},
            {0, 0, 1, 0},
            {0, 0, 0, 1}
        };
        while (n > 0) {
            if ((n & 1) != 0) {
                matn = mulMatrix(matn, mat);
            }
            mat = mulMatrix(mat, mat);
            n >>= 1;
        }
        return matn[3][3];
    }

    public int[][] mulMatrix(int[][] m1, int[][] m2) {
        int n1 = m1.length, n2 = m2.length, n3 = m2[0].length;
        int[][] res = new int[n1][n3];
        for (int i = 0; i < n1; i++) {
            for (int k = 0; k < n3; k++) {
                for (int j = 0; j < n2; j++) {
                    res[i][k] = (int) ((res[i][k] + (long) m1[i][j] * m2[j][k]) % MOD);
                }
            }
        }
        return res;
    }
}

  另外比较离谱的面向结果编程。

class Solution {
    public int numTilings(int n) {
        if(n==1) return 1;if(n==2) return 2;if(n==3) return 5;if(n==4) return 11;if(n==5) return 24;if(n==6) return 53;if(n==7) return 117;if(n==8) return 258;if(n==9) return 569;if(n==10) return 1255; if(n==20) return 3418626;if(n==30) return 312342182;if(n==40) return 833773577;if(n==50) return 451995198;if(n==60) return 882347204;if(n==70) return 155521223;if(n==80) return 621192477;if(n==90) return 632727593; if(n==100) return 190242381;if(n==119) return 853328156; if(n==211) return 374315309;if(n==232) return 25197135;if(n==262) return 718490430; if(n==428) return 401892698;if(n==449) return 288656278; if(n==500) return 603582422;if(n==574) return 461429539; if(n==630) return 189827198;if(n==668) return 218895443;if(n==694) return 74178564;if(n==699) return 939053561; if(n==700) return 637136622;if(n==728) return 217951151;if(n==758) return 446953183; if(n==802) return 473826217;if(n==814) return 443572580;if(n==829) return 969408247;if(n==865) return 305566409; if(n==951) return 326538883; if(n==1000) return 979232805; return 0;
    }
}