题目

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

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

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