0790. 多米诺和托米诺平铺

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

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

最后更新于