友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
790. 多米诺和托米诺平铺
有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L"
的托米诺形。两种形状都可以旋转。
给定整数 n，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。
平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。
示例 1:
输入: n = 3 输出: 5 解释: 五种不同的方法如上所示。
示例 2:
输入: n = 1 输出: 1
提示：
-
1 <= n <= 1000
思路分析
| 还是要画图分析思路才更容易理顺！ |
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-06-23 22:58:13
*/
private static final int MOD = 1_000_000_007;
public int numTilings(int n) {
int[] memo = new int[n + 3];
memo[1] = 1;
memo[2] = 2;
memo[3] = 5;
return dfs(n, memo);
}
private int dfs(int n, int[] memo) {
if (memo[n] > 0) {
return memo[n];
}
long sum = 0L;
sum += dfs(n - 3, memo);
sum += 2L * dfs(n - 1, memo);
return memo[n] = (int) (sum % MOD);
}