【LeetCode】Day181-多米诺和托米诺平铺

题目

790. 多米诺和托米诺平铺【中等】

题解

属实是完全分析不出来的动态规划了…来看看官解怎么说

第 i 列的正方形有以下四种情况：

• 一个正方形都没有被覆盖，记为状态 0；
• 只有上方的正方形被覆盖，记为状态 1；
• 只有下方的正方形被覆盖，记为状态 2；
• 上下两个正方形都被覆盖，记为状态 3。

1. 状态定义：dp[i][s] 平铺到第 i 列时，各个状态 s 对应的平铺方法数量。
2. 状态转移方程：如下图，红色表示新铺的瓷砖，左边状态[i]=右边几种状态[i-1]的加和

3. 初始条件：dp[0][3]=1，其余dp均为0

4. 返回值：dp[n][3]

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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：$O(n)$

空间复杂度：$O(n)$