面對(duì)人生的煩惱與挫折，最重要的是擺正自己的心態(tài)，積極面對(duì)一切。再苦再
累，也要保持微笑。笑一笑，你的人生會(huì)更美好!

參考 790. 多米諾和托米諾平鋪，難度分1830。

題目

有兩種形狀的瓷磚：一種是 2 x 1 的多米諾形，另一種是形如 "L" 的托米諾形。兩種形狀都可以旋轉(zhuǎn)。

兩種多米諾

給定整數(shù) n ，返回可以平鋪 2 x n 的面板的方法的數(shù)量。返回對(duì) 109 + 7 取模 的值。

平鋪指的是每個(gè)正方形都必須有瓷磚覆蓋。兩個(gè)平鋪不同，當(dāng)且僅當(dāng)面板上有四個(gè)方向上的相鄰單元中的兩個(gè)，使得恰好有一個(gè)平鋪有一個(gè)瓷磚占據(jù)兩個(gè)正方形。

示例

輸入: n = 3
輸出: 5
解釋: 五種不同的方法如上所示。

解題思路

• 動(dòng)態(tài)規(guī)劃：動(dòng)態(tài)規(guī)劃重要的是找到所有轉(zhuǎn)移狀態(tài)和轉(zhuǎn)移方程，本題可把最后的多米諾可能的組成形式作為轉(zhuǎn)移狀態(tài)。
• 找公式規(guī)律：如果動(dòng)態(tài)規(guī)劃只設(shè)定一維dp[i],則可以找到規(guī)律dp[i] =2*dp[i-1]+dp[i-3]。

動(dòng)態(tài)規(guī)劃 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];
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，一次循環(huán)遍歷。
• 空間復(fù)雜度：O(n)，dp數(shù)組空間4(n+1)。

找規(guī)律 0ms

class Solution {
    public int numTilings(int n) {
        //找規(guī)律 
        //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];
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，一次循環(huán)遍歷。
• 空間復(fù)雜度：O(n)，dp數(shù)組空間n+1。

2023-04-09