LeetCode 790. 多米诺和托米诺平铺（动态规划）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

有两种形状的瓷砖：
一种是 2x1 的多米诺形，
另一种是形如 “L” 的托米诺形。
两种形状都可以旋转。

XX <- 多米诺XX <- "L" 托米诺 X

给定 N 的值，有多少种方法可以平铺 2 x N 的面板？返回值 mod 10^9 + 7。

（平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。）

示例: 输入: 3 输出: 5 解释: 下面列出了五种不同的方法，不同字母代表不同瓷砖： XYZ XXZ XYY XXY XYY XYZ YYZ XZZ XYY XXY提示： N 的范围是 [1, 1000]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/domino-and-tromino-tiling
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

状态转移如下：

class Solution { public:int numTilings(int N) {if(N == 1) return 1;vector<vector<long long>> dp(N+1, vector<long long>(4, 0));dp[0][0] = 1;int mod = 1e9+7;for(int i = 1; i <= N; i++){dp[i][0] = (dp[i-1][0]+dp[i-1][3])%mod;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]+dp[i-1][2])%mod;}return dp[N][0];} };

8 ms 7.6 MB C++

当前状态只跟前一次的状态有关，可以压缩空间至 O(1)

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的LeetCode 790. 多米诺和托米诺平铺（动态规划）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。