阿狗工具

面对人生的烦恼与挫折，最重要的是摆正自己的心态，积极面对一切。再苦再
累，也要保持微笑。笑一笑，你的人生会更美好!

参考 790. 多米诺和托米诺平铺，难度分1830。

题目

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

两种多米诺

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

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

示例

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

解题思路

• 动态规划：动态规划重要的是找到所有转移状态和转移方程，本题可把最后的多米诺可能的组成形式作为转移状态。
• 找公式规律：如果动态规划只设定一维dp[i],则可以找到规律dp[i] =2*dp[i-1]+dp[i-3]。

动态规划 1ms

class Solution {
    int MOD = (int)(1e9+7);
    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];
    }
}

复杂度分析

• 时间复杂度：O(n)，一次循环遍历。
• 空间复杂度：O(n)，dp数组空间4(n+1)。

找规律 0ms

class Solution {
    public int numTilings(int n) {
        //找规律 
        //sumDp[i]=sumDp[i-1]+sumDp[i-2]+2(sumDp[i-3]+sumDp[i-4]+..+sumDp[1]) + 2
        //sumDp[i-1]=sumDp[i-2]+sumDp[i-3]+2(sumDp[i-4]+sumDp[i-5]+..+sumDp[1]) + 2
        //sumDp[i]-sumDp[i-1]=sumDp[i-1]+sumDp[i-3]-->sumDp[i]=2*sumDp[i-1]+sumDp[i-3]
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n == 3) return 5;
        int[] sumDp = new int[n + 1];
        sumDp[1] = 1;
        sumDp[2] = 2;
        sumDp[3] = 5;
        for(int i = 4; i < sumDp.length; i++) {
            sumDp[i] = (int)((2*sumDp[i-1]%(1e9 + 7)+sumDp[i-3]%(1e9 + 7))%(1e9 + 7));
        }
        return sumDp[n];
    }
}

复杂度分析

• 时间复杂度：O(n)，一次循环遍历。
• 空间复杂度：O(n)，dp数组空间n+1。

2023-04-09