Skip to content

Latest commit

 

History

History
168 lines (108 loc) · 6.61 KB

790.domino-and-tromino-tiling.md

File metadata and controls

168 lines (108 loc) · 6.61 KB
Raw

题目地址(790. 多米诺和托米诺平铺)

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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。