题目描述
有两种形状的瓷砖:一种是 2x1 的多米诺形,另一种是形如 “L” 的托米诺形。两种形状都可以旋转。
XX <- 多米诺
XX <- "L" 托米诺
X
给定 N 的值,有多少种方法可以平铺 2 x N 的面板?返回值模 10^9 + 7。
(平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同,当且仅当面板上有四个方向上的相邻单元中的两个,使得恰好有一个平铺有一个瓷砖占据两个正方形。)
样例
输入: 3
输出: 5
解释:
下面列出了五种不同的方法,不同字母代表不同瓷砖:
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY
限制
- N 的范围是
[1, 1000]
。
算法
(动态规划) $O(n)$
- 状态 $f(i, 0)$ 表示 $i$ 之前的列都已经铺满了,第 $i$ 列没有铺任何瓷砖的方案数;$f(i, 1)$ 表示 $i$ 之前的列都已经铺满了,第 $i$ 列只铺了第一层的瓷砖的方案数;同理,$f(i, 2) 表示只铺了第二层的瓷砖的方案数,$f(i, 3)$ 表示第 $i$ 列的两层都铺了瓷砖的方案数。
- 初始时,$f(0, 0) = 1, f(0, 3) = 1$,其余都为 0。这是因为这两种状态各有一种铺法。
- 转移时,对于 $f(i, 0)$,只能从 $f(i - 1, 3)$ 累加,因为要保证 $i$ 之前的列是满的才可以转移。通过枚举,不难发现,$f(i, 1) = f(i - 1, 0) + f(i - 1, 2)$,$f(i, 2) = f(i - 1, 0) + f(i - 1, 1)$,分别对应了两个不同情况的第 $i - 1$ 行,我们第 $i$ 行都有一种方式铺,所以可以转移。最后 $f(i, 3) = f(i - 1, 0) + f(i - 1, 1) + f(i - 1, 2) + f(i - 1, 3)$,也就是说对于 $i - 1$ 行的任何一种铺法,我们都有一种方法让 $i - 1$ 行铺满的同时,让第 $i$ 行的两层也都铺上瓷砖。
- 最终答案显然为 $f(N - 1, 3)$。
时间复杂度
- 状态数为 $O(n)$ 个,转移仅需要常数时间,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的空间记录状态。
C++ 代码
class Solution {
public:
int numTilings(int N) {
const int mod = 1000000007;
vector<vector<int>> f(N, vector(4, 0));
f[0][0] = 1;
f[0][3] = 1;
for (int i = 1; i < N; i++) {
f[i][0] = f[i - 1][3];
f[i][1] = (f[i - 1][0] + f[i - 1][2]) % mod;
f[i][2] = (f[i - 1][0] + f[i - 1][1]) % mod;
f[i][3] = ((( f[i - 1][0]
+ f[i - 1][1]) % mod
+ f[i - 1][2]) % mod
+ f[i - 1][3]) % mod;
}
return f[N - 1][3];
}
};
就回复个牛逼吧