Leetcode 790 铺瓷砖

题目概述

Leetcode 790

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 10^9 + 7.

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

Constraints:

• 1 <= n <= 1000

思路

乍一看这题有些摸不着头脑，总之先归纳一下n在1~3这个范围内时铺瓷砖的情况。

n = 3时，可以分为三种情况去统计可能的铺瓷砖方式：

• 将瓷砖分为2 x 2和2 x 1的左右两部分，此时左半边根据n = 2的结果可以得知有两种铺法
• 将瓷砖分为2 x 1和2 x 2的左右两部分，其中右半部分按照横向的1 x 2形状进行分割（否则会和前一种情况重复）
• 最后是不利用之前结果的铺法，也就是n = 3时的特有铺法

我们可以再看一下n = 4和n = 5时的情况

还是采用类似的思考方式，这时可以发现规律了。若令$a_n$表示地面为2 x n时可能的铺瓷砖方式总数，那么有:

$$a_n = \begin{cases} 1 \qquad&, n = 1\\ 2 &, n = 2\\ 5 &, n = 3\\ a_{n - 1} + a_{n - 2} + 2 \sum_{k = 1}^{n - 3} a_k + 2 &, n > 3 \\ \end{cases}$$

或者可以简化成：

$$a_n = \begin{cases} 1 \qquad&, n = 0\\ 1 &, n = 1\\ 2 &, n = 2\\ a_{n - 1} + a_{n - 2} + 2 \sum_{k = 0}^{n - 3} a_k &, n \geq 3 \\ \end{cases}$$

那么这其实是一道动态规划的题目，只不过想要准确地找出状态转移方程还是有点难度。不过，到这一步为止感觉还是不够，因为求解的话还需要对之前所有的情况进行求和，太麻烦了。所以再考察一下相邻项之间是否存在一些联系。

$$a_{n - 1} = a_{n - 2} + a_{n - 3} + 2 \sum_{k = 0}^{n - 4} a_k \qquad, n \geq 4$$

等式两边同时加上 $a_{n - 3}$, 可得:

$$a_{n - 1} + a_{n - 3} = a_{n - 2} + 2 \sum_{k = 0}^{n - 3} a_k$$

于是有，

$$\begin{aligned} a_n &= a_{n - 1} + a_{n - 1} + a_{n - 3} \\ &= 2 a_{n - 1} + a_{n - 3} \end{aligned}$$

这便是最终的状态转移方程了。最后看一下代码实现。

代码实现

class Solution:
    def numTilings(self, n: int) -> int:
        if n < 3:
            return n
        else:
            dp = [0] * (n + 1)
            dp[0], dp[1], dp[2] = 1, 1, 2

            for i in range(3, n+1):
                dp[i] = 2 * dp[i-1] + dp[i-3]

            return dp[-1] % (10 ** 9 + 7)

顺利通过。