本文主要是介绍力扣 790. 多米诺和托米诺平铺（一维dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
有两种形状的瓷砖：一种是 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的方案数目}
};这篇关于力扣 790. 多米诺和托米诺平铺（一维dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
