0790：多米诺和托米诺平铺（1830 分）

2017-02-28 约 493 字预计阅读 1 分钟次阅读

力扣第 790 题

题目

有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。

给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 10⁹ + 7 取模的值。

平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。

示例 1:

输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。

示例 2:

输入: n = 1
输出: 1

提示：

1 <= n <= 1000

分析

假设最后一列竖着铺 1x2，显然转为递归子问题，横着铺两个 1x2，也同理。

假如最后一列铺 ‘L’ 性，则要求平铺 2x(n-1) 但最后一列只铺一个的方法数。

为了方便递推，令：

dp[i][0] 代表平铺 i-1 列的方法数
dp[i][1] 代表平铺 i 列但最后一列只铺一个的方法数
dp[i][2] 代表平铺 i 列的方法数

即可由 dp[i] 递推出 dp[i+1]。还可以优化为 3 个变量。

解答

1
2
3
4
5


def numTilings(self, n: int) -> int:
    a, b, c, mod = 0, 0, 1, 10**9+7
    for _ in range(n):
        a, b, c = c, (2*a+b)%mod, (a+b+c)%mod
    return c

36 ms

*附加

这是完全的线性递推关系，因此可以用矩阵快速幂优化。

注意在矩阵乘法时也取模即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


def numTilings(self, n: int) -> int:
    def mpow(mat, n):
        res = mat
        for bit in bin(n)[3:]:
            res = res*res%mod
            if bit=='1':
                res = res*mat%mod
        return res

    import numpy as np
    mod = 10**9+7
    A = np.mat([[0,0,1],[2,1,0],[1,1,1]])
    dp = np.mat([[0],[0],[1]])
    dp = mpow(A, n)*dp
    return int(dp[-1])%mod

76 ms

目录

0790：多米诺和托米诺平铺（1830 分）

题目

分析

解答

*附加