题目描述:
有两种形状的瓷砖:一种是 2 x 1
的多米诺形,另一种是形如 "L" 的托米诺形。两种形状都可以旋转。
给定整数 n ,返回可以平铺 2 x n
的面板的方法的数量。返回对 109 + 7
取模 的值。
平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同,当且仅当面板上有四个方向上的相邻单元中的两个,使得恰好有一个平铺有一个瓷砖占据两个正方形。
示例 1:
输入: n = 3 输出: 5 解释: 五种不同的方法如上所示。
示例 2:
输入: n = 1 输出: 1
提示:
1 <= n <= 1000
思路:
一眼动态规划
很容易想到,考虑第i列的平铺方式。
设计一个二维数组dp[i][j],表示以i列结尾的状态j的平铺方式的组合数目
第i列的情况有以下几种:
一个正方形都没有,记为状态 0,用dp[i][0]表示
只有上方的正方形,记为状态 1,用dp[i][1]表示
只有下方的正方形,记为状态 2,用dp[i][2]表示
上下两个正方形都有,记为状态 3,用dp[i][3]表示
那么第i列的这几种情况怎么由第i-1列的状态转移过来的呢?
dp[i][0]=dp[i-1][3]
dp[i][1]=dp[i-1][0]+dp[i-1][2];
dp[i][2]=dp[i-1][0]+dp[i-1][1];
dp[i][3]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]
这里只解释dp[i][1]
初始化,dp[0][0]=dp[0][1]=dp[0][2]=0,dp[0][3]=1
代码:
const int mod=1e9+7;
class Solution {
public:
int numTilings(int n) {
vector<vector<int>> dp(n+1,vector<int>(4));//定义dp二维数组
//初始化
dp[0][0]=0;
dp[0][1]=0;
dp[0][2]=0;
dp[0][3]=1;
for(int i=1;i<=n;i++){//题目要求取模,说明答案较大,考虑溢出问题
dp[i][0]=dp[i-1][3]%mod;
dp[i][1]=((long long)dp[i-1][2]+dp[i-1][0])%mod;
dp[i][2]=((long long)dp[i-1][1]+dp[i-1][0])%mod;
dp[i][3]=((long long)dp[i-1][3]+dp[i-1][0]+dp[i-1][2]+dp[i-1][1])%mod;
}
return dp[n][3];//dp[n][3]表示覆盖到了第n列,且状态为3的方案数目
}
};