0790. 多米诺和托米诺平铺
https://leetcode-cn.com/problems/domino-and-tromino-tiling/
有两种形状的瓷砖：一种是 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:
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)$，大家可以试试。
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 8mo ago