【2022-11-12每日一题】790. 多米诺和托米诺平铺[Medium]
2022-11-12
2分钟阅读时长
2022-11-12每日一题：790. 多米诺和托米诺平铺
难度：Medium
标签：动态规划
有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。
给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。
平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。
示例 1:
输入: n = 3 输出: 5 解释: 五种不同的方法如上所示。
示例 2:
输入: n = 1 输出: 1
提示：
1 <= n <= 1000
方法一：动态规划
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
代码
func numTilings(n int) int {
const mod int = 1e9+7
dp := make([][4]int, n+1)
dp[0][3] = 1
for i := 1; i <= n; i++ {
dp[i][0] = dp[i-1][3] // 一个正方形都没有被覆盖，记为状态 0
dp[i][1] = (dp[i-1][0] + dp[i-1][2])%mod// 只有上方的正方形被覆盖，记为状态 1
dp[i][2] = (dp[i-1][0] + dp[i-1][1])%mod// 只有下方的正方形被覆盖，记为状态 2
// 上下两个正方形都被覆盖，记为状态 3
dp[i][3] = (((dp[i-1][0] + dp[i-1][1])%mod + dp[i-1][2])%mod + dp[i-1][3])%mod
}
return dp[n][3]
}
复杂度分析
时间复杂度：O(n)，其中 n 是总列数。
空间复杂度：O(n)。保存 dp 数组需要 O(n) 的空间。
方法二：矩阵快速幂
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
代码
const mod int = 1e9 + 7
type matrix [4][4]int
func (a matrix) mul(b matrix) matrix {
c := matrix{}
for i, row := range a {
for j := range b[0] {
for k, v := range row {
c[i][j] = (c[i][j] + v*b[k][j]) % mod
}
}
}
return c
}
func (a matrix) pow(n int) matrix {
res := matrix{}
for i := range res {
res[i][i] = 1
}
for ; n > 0; n >>= 1 {
if n&1 > 0 {
res = res.mul(a)
}
a = a.mul(a)
}
return res
}
func numTilings(n int) int {
m := matrix{
{0, 0, 0, 1},
{1, 0, 1, 0},
{1, 1, 0, 0},
{1, 1, 1, 1},
}
return m.pow(n)[3][3]
}
复杂度分析
时间复杂度：O(logn)，其中 n 是总列数。矩阵快速幂的时间复杂度为 O(logn)。
空间复杂度：O(1)。
LeetCode题库地址
此题还需继续理解，暂未掌握