第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
0790. 多米诺和托米诺平铺
题目地址(790. 多米诺和托米诺平铺)
题目描述
1
有两种形状的瓷砖：一种是 2x1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。
2
3
XX <- 多米诺
4
5
XX <- "L" 托米诺
6
X
7
8
9
给定 N 的值，有多少种方法可以平铺 2 x N 的面板？返回值 mod 10^9 + 7。
10
11
（平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。）
12
13
示例:
14
输入: 3
15
输出: 5
16
解释:
17
下面列出了五种不同的方法，不同字母代表不同瓷砖：
18
XYZ XXZ XYY XXY XYY
19
XYZ YYZ XZZ XYY XXY
20
21
提示：
22
23
N 的范围是 [1, 1000]
Copied!
前置知识
- 动态规划
公司
- 暂无
思路
这种题目和铺瓷砖一样，这种题目基本都是动态规划可解。做这种题目的诀窍就是将所有的可能都列举出来，然后分析问题的最优子结构。最后根据子问题之间的递推关系解决问题。
如果题目只有 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 在什么情况下使用。
根据以上的信息有如下公式:
1
F(n) = F(n-1) + F(n-2) + 2 * T(n-1)
Copied!
由于上述等式有两个变量，因此至少需要两个这样的等式才可解。而上面的等式是 F(n) = xxx，因此一个直觉找到一个类似 T(n) = xxx 的公式。不难发现如下等式：
1
T(n) = 2 * F(n-2) + T(n-1)
Copied!
乘以 2 是因为最后一块可以选择 4 或者 6 任意一块
将上面两个公式进行合并。具体来说就是：
1
F(n) = F(n-1) + F(n-2) + 2 * T(n-1) ①
2
T(n) = 2 * F(n-2) + T(n-1) ②
3
将 ② 的 n 替换为 n - 1得：
4
T(n-1) = 2 * F(n-3) + T(n-2) ③
5
将 ③ 两侧乘以 2 得：
6
2 * T(n-1) = 4 * F(n-3) + 2 * T(n-2) ④
Copied!
将 ④ 代入 ① 得：
1
F(n) = F(n-1) + F(n-2) + 4 * F(n-3) + 2 * T(n-2)
2
将 4*F(n-3) 拆分为 F(n-3) + 3 * F(n-3) 并移动式子顺序得：
3
F(n) = F(n-2) + F(n-3) + 2 * T(n-2) + F(n-1) + 3 * F(n-3)
4
将 F(n-2) + F(n-3) + 2 * T(n-2) 替换为 F(n-1) 得：
5
F(n)= 2 * F(n-1) + F(n-3)
Copied!
至此，我们得出了状态转移方程：
1
F(n) = 2 * F(n-1) + F(n-3)
Copied!
关键点
- 识别最优子结构
- 对一块瓷砖能拼成的图形进行分解，并对每一种情况进行讨论
代码
- 语言支持：Python3
Python3 Code:
1
class Solution:
2
def numTilings(self, N: int) -> int:
3
dp = [0] * (N + 3)
4
# f(3) = 2 * f(2) + f(0) = 2 + f(0) = 1 -> f(0) = -1
5
# f(4) = 2 * f(3) + f(1) = 2 + f(1) = 2 -> f(1) = 0
6
dp[0] = -1
7
dp[1] = 0
8
dp[2] = 1
9
# f(n) = f(n-1) + f(n-2) + 2 * T(n-1)
10
# 2 * T(n-1) = 2 * f(n-3) + 2 * T(n-2)
11
# 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)
12
for i in range(3, N + 3):
13
dp[i] = 2 * dp[i-1] + dp[i-3]
14
return dp[-1] % (10 ** 9 + 7)
Copied!
复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
使用滚动数组优化可以将空间复杂度降低到 $O(1)$，大家可以试试。
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago