
题目描述
有两种形状的瓷砖:一种是 2 x 1
的多米诺形,另一种是形如 "L" 的托米诺形。两种形状都可以旋转。

给定整数 n ,返回可以平铺 2 x n
的面板的方法的数量。返回对 109 + 7
取模 的值。
平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同,当且仅当面板上有四个方向上的相邻单元中的两个,使得恰好有一个平铺有一个瓷砖占据两个正方形。
示例 1:

输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。
示例 2:
输入: n = 1
输出: 1
提示:
解法
方法一:动态规划
我们首先要读懂题意,题目实际上是让我们求铺满 \(2\times n\) 的面板的方案数,其中面板上的每个正方形只能被一个瓷砖覆盖。
瓷砖的形状有两种,分别是 2 x 1
型 和 L
型,并且两种瓷砖都可以旋转。我们将旋转后的瓷砖分别记为 1 x 2
型 和 L'
型。
我们定义 \(f[i][j]\) 表示平铺前 \(2\times i\) 的面板,其中 \(j\) 表示最后一列的状态。最后一列有 \(4\) 种状态,分别是:
- 最后一列铺满,记为 \(0\)
- 最后一列只铺了上方一个瓷砖,记为 \(1\)
- 最后一列只铺了下方一个瓷砖,记为 \(2\)
- 最后一列没有铺瓷砖,记为 \(3\)
那么答案就是 \(f[n][0]\)。初始时 \(f[0][0]=1\),其余 \(f[0][j]=0\)。
我们考虑铺到第 \(i\) 列,来看看状态转移方程:
当 \(j=0\) 时,最后一列铺满,可由前一列的 \(0,1,2,3\) 四种状态铺上对应的瓷砖转移而来,即 \(f[i-1][0]\) 铺上 1 x 2
型瓷砖,或者 \(f[i-1][1]\) 铺上 L'
型瓷砖,或者 \(f[i-1][2]\) 铺上 L'
型瓷砖,或者 \(f[i-1][3]\) 铺上两块 2 x 1
型瓷砖。因此 \(f[i][0]=\sum_{j=0}^3f[i-1][j]\)。
当 \(j=1\) 时,最后一列只铺了上方一个瓷砖,可由前一列的 \(2,3\) 两种状态转移而来,即 \(f[i-1][2]\) 铺上 2 x 1
型瓷砖,或者 \(f[i-1][3]\) 铺上 L
型瓷砖。因此 \(f[i][1]=f[i-1][2]+f[i-1][3]\)。
当 \(j=2\) 时,最后一列只铺了下方一个瓷砖,可由前一列的 \(1,3\) 两种状态转移而来,即 \(f[i-1][1]\) 铺上 2 x 1
型瓷砖,或者 \(f[i-1][3]\) 铺上 L'
型瓷砖。因此 \(f[i][2]=f[i-1][1]+f[i-1][3]\)。
当 \(j=3\) 时,最后一列没有铺瓷砖,可由前一列的 \(0\) 一种状态转移而来。因此 \(f[i][3]=f[i-1][0]\)。
可以发现,状态转移方程中只涉及到前一列的状态,因此我们可以使用滚动数组优化空间复杂度。
注意,过程中的状态数值可能会很大,因此需要对 \(10^9+7\) 取模。
时间复杂度 \(O(n)\),其中 \(n\) 为面板的列数。空间复杂度 \(O(1)\)。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def numTilings(self, n: int) -> int:
f = [1, 0, 0, 0]
mod = 10**9 + 7
for i in range(1, n + 1):
g = [0] * 4
g[0] = (f[0] + f[1] + f[2] + f[3]) % mod
g[1] = (f[2] + f[3]) % mod
g[2] = (f[1] + f[3]) % mod
g[3] = f[0]
f = g
return f[0]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public int numTilings(int n) {
long[] f = {1, 0, 0, 0};
int mod = (int) 1e9 + 7;
for (int i = 1; i <= n; ++i) {
long[] g = new long[4];
g[0] = (f[0] + f[1] + f[2] + f[3]) % mod;
g[1] = (f[2] + f[3]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[0];
f = g;
}
return (int) f[0];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public:
int numTilings(int n) {
const int mod = 1e9 + 7;
long long f[4] = {1, 0, 0, 0};
for (int i = 1; i <= n; ++i) {
long long g[4];
g[0] = (f[0] + f[1] + f[2] + f[3]) % mod;
g[1] = (f[2] + f[3]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[0];
memcpy(f, g, sizeof(g));
}
return f[0];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | func numTilings(n int) int {
f := [4]int{}
f[0] = 1
const mod int = 1e9 + 7
for i := 1; i <= n; i++ {
g := [4]int{}
g[0] = (f[0] + f[1] + f[2] + f[3]) % mod
g[1] = (f[2] + f[3]) % mod
g[2] = (f[1] + f[3]) % mod
g[3] = f[0]
f = g
}
return f[0]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | function numTilings(n: number): number {
const mod = 1_000_000_007;
let f: number[] = [1, 0, 0, 0];
for (let i = 1; i <= n; ++i) {
const g: number[] = Array(4);
g[0] = (f[0] + f[1] + f[2] + f[3]) % mod;
g[1] = (f[2] + f[3]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[0] % mod;
f = g;
}
return f[0];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | impl Solution {
pub fn num_tilings(n: i32) -> i32 {
const MOD: i64 = 1_000_000_007;
let mut f: [i64; 4] = [1, 0, 0, 0];
for _ in 1..=n {
let mut g = [0i64; 4];
g[0] = (f[0] + f[1] + f[2] + f[3]) % MOD;
g[1] = (f[2] + f[3]) % MOD;
g[2] = (f[1] + f[3]) % MOD;
g[3] = f[0] % MOD;
f = g;
}
f[0] as i32
}
}
|