# 0790. 多米诺和托米诺平铺
### 题目地址(790. 多米诺和托米诺平铺)
### 题目描述
```
有两种形状的瓷砖：一种是 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]
```
### 前置知识
* 动态规划
### 公司
* 暂无
### 思路
这种题目和铺瓷砖一样，这种题目基本都是动态规划可解。做这种题目的诀窍就是将所有的可能都列举出来，然后分析问题的最优子结构。最后根据子问题之间的递推关系解决问题。
如果题目只有 XX 型，或者只有 L 型，实际上就很简单了。而这道题是 XX 和 L，则稍微有点难度。力扣还有一些其他更复杂度的铺瓷砖，都是给你若干瓷砖，让你刚好铺满一个形状。大家做完这道题之后可以去尝试一下其他题相关目。
以这道题来说，所有可能的情况无非就是以下 6 种：
而题目要求的是**刚好铺满** 2 \* N 的情况的总的可能数。
如上图 1，2，3，5 可能是刚好铺满 2 \_ N 的瓷砖的**最后一块砖**，换句话说 4 和 6 不能是刚好铺满 2 \_ N 的最后一块瓷砖。
为了方便描述，我们令 F(n) 表示刚好铺满 2 \* n 的瓷砖的总的可能数，因此题目要求的其实就是 F(n)。
* 如果最后一块选择了形状 1，那么**此时**的刚好铺满 2 \* n 的瓷砖的总的可能数是 F(n-2)
* 如果最后一块选择了形状 2，那么**此时**的刚好铺满 2 \* n 的瓷砖的总的可能数是 F(n-1)
* 如果最后一块选择了形状 3，那么**此时**的刚好铺满 2 \* n 的瓷砖的总的可能数是 ?
* 如果最后一块选择了形状 5，那么**此时**的刚好铺满 2 \* n 的瓷砖的总的可能数是 ?
* 如果最后一块选择了形状 4 和 6，那么**此时**的刚好铺满 2 \* n 的瓷砖的总的可能数是 0。换句话说 4 和 6 不可能是刚好铺满的最后一块砖。
虽然 4 和 6 不可能是刚好铺满的最后一块砖，但其实可以是中间状态，中间状态可以进一步转移到**刚好铺满的状态**。比如股票问题就是这样，虽然我们的最终答案不可能是买入之后，一定是卖出，但是中间的过程可以卖出，通过卖出转移到最终状态。
现在的问题是如何计算：最后一块选择了形状 3 和 最后一块选择了形状 5 的总的可能数，以及 4 和 6 在什么情况下选择。实际上，我们只需要考虑选择我 3 和 5 的总的可能数就行了，其原因稍后你就知道了。
为了表示所有的情况，我们需要另外一个状态定义和转移。 我们令 T(n) 表示刚好铺满 2 \* (N - 1)瓷砖，最后一列只有一块瓷砖的总的可能数。对应上图中的 4 和 6。
经过这样的定义，那么就有：
* 如果倒数第二块选择了形状 4，那么最后一块选择形状 3 刚好铺满 2 \* N 瓷砖。
* 如果倒数第二块选择了形状 6，那么最后一块选择形状 5 刚好铺满 2 \* N 瓷砖。
> 大家可以根据基本图形画一下试试就知道了。同时你也应该理解了 4 和 6 在什么情况下使用。
根据以上的信息有如下公式:
```
F(n) = F(n-1) + F(n-2) + 2 * T(n-1)
```
由于上述等式有两个变量，因此至少需要两个这样的等式才可解。而上面的等式是 F(n) = xxx，因此一个直觉找到一个类似 T(n) = xxx 的公式。不难发现如下等式：
```
T(n) = 2 * F(n-2) + T(n-1)
```
> 乘以 2 是因为最后一块可以选择 4 或者 6 任意一块
将上面两个公式进行合并。具体来说就是：
```
F(n) = F(n-1) + F(n-2) + 2 * T(n-1) ①
T(n) = 2 * F(n-2) + T(n-1) ②
将 ② 的 n 替换为 n - 1得：
T(n-1) = 2 * F(n-3) + T(n-2) ③
将 ③ 两侧乘以 2 得：
2 * T(n-1) = 4 * F(n-3) + 2 * T(n-2) ④
```
将 ④ 代入 ① 得：
```
F(n) = F(n-1) + F(n-2) + 4 * F(n-3) + 2 * T(n-2)
将 4*F(n-3) 拆分为 F(n-3) + 3 * F(n-3) 并移动式子顺序得：
F(n) = F(n-2) + F(n-3) + 2 * T(n-2) + F(n-1) + 3 * F(n-3)
将 F(n-2) + F(n-3) + 2 * T(n-2) 替换为 F(n-1) 得：
F(n)= 2 * F(n-1) + F(n-3)
```
至此，我们得出了状态转移方程：
```
F(n) = 2 * F(n-1) + F(n-3)
```
### 关键点
* 识别最优子结构
* 对一块瓷砖能拼成的图形进行分解，并对每一种情况进行讨论
### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def numTilings(self, N: int) -> int:
dp = [0] * (N + 3)
# f(3) = 2 * f(2) + f(0) = 2 + f(0) = 1 -> f(0) = -1
# f(4) = 2 * f(3) + f(1) = 2 + f(1) = 2 -> f(1) = 0
dp[0] = -1
dp[1] = 0
dp[2] = 1
# f(n) = f(n-1) + f(n-2) + 2 * T(n-1)
# 2 * T(n-1) = 2 * f(n-3) + 2 * T(n-2)
# f(n) = f(n-1) + 2 * f(n-3) + f(n-2) + 2T(n-2) = f(n-1) + f(n-3) + f(n-3) + f(n-2) + 2T(n-2) = f(n-1) + f(n-3) + f(n-1) = 2 * f(n-1) + f(n-3)
for i in range(3, N + 3):
dp[i] = 2 * dp[i-1] + dp[i-3]
return dp[-1] % (10 ** 9 + 7)
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：$O(n)$
使用滚动数组优化可以将空间复杂度降低到 $O(1)$，大家可以试试。
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/790.domino-and-tromino-tiling.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.