Java实现 LeetCode 790 多米诺和托米诺平铺（递推）

790. 多米诺和托米诺平铺

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

XX <- 多米诺

XX <- “L” 托米诺

X

给定 N 的值，有多少种方法可以平铺 2 x N 的面板？返回值 mod 10^9 + 7。

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

示例:

输入: 3

输出: 5

解释:

下面列出了五种不同的方法，不同字母代表不同瓷砖：

XYZ XXZ XYY XXY XYY

XYZ YYZ XZZ XYY XXY

提示：

N 的范围是 [1, 1000]

class Solution {

    //dp[i][0]是第n行，并且是平铺

    //dp[i][1]是第n行，不平铺的

    // public int numTilings(int N) {

    //     long[][] dp = new long[N+1][3];

    //     dp[0][0] = 1;

    //     dp[0][1] = 0;

    //     int MOD = 1000000007;

    //     for(int i = 1 ; i <= N ; ++i){

    //         long temp = i < 2 ? 0 : dp[i -2][0];

    //         dp[i][0] = (temp + dp[i-1][0] + 2 * dp[i-1][1]) % MOD;

    //         dp[i][1] = (temp +dp[i-1][1]) % MOD;

    //     }

    //     return (int)dp[N][0];

    // }

    public int numTilings(int N) {

         int mod = 1000000007;

        int[] dp = new int[N+3];

        dp[0] = 1;

        dp[1] = 1;

        dp[2] = 2;

        dp[3] = 5;

        for(int i = 4; i <= N; i++){

            //这里全是平铺的，

            //我当前这一位，可以是我上一位平铺的+一个2*1的，

            //我可以把1*2的放到最上面，也可以放在最下面，是两种可能，所以*2

            //还可以是我三位前的那个，因为可以是两个L

            //但这里，我开头或者结尾可能是L的，如果我们在那个基础上加上L

            //可能会导致重复，以至于要/2，也就变成了三位前的那个*2/2==1

            dp[i] = (2*(dp[i-1] % mod) % mod + dp[i-3] % mod) % mod;

        }

        return dp[N] % mod;

    }

}

巴特西

Java实现 LeetCode 790 多米诺和托米诺平铺（递推）

790. 多米诺和托米诺平铺

最新文章

热门文章