友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
2320. 统计放置房子的方式数
一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。
现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。
注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。
示例 1：
输入：n = 1 输出：4 解释： 可能的放置方式： 1. 所有地块都不放置房子。 2. 一所房子放在街道的某一侧。 3. 一所房子放在街道的另一侧。 4. 放置两所房子，街道两侧各放置一所。
示例 2：
输入：n = 2 输出：9 解释：如上图所示，共有 9 种可能的放置方式。
提示：
-
1 <= n <= 104
思路分析
先只考虑一边的情况，再组合两边的情况。只考虑一边的情况，就是一个斐波那契数列： \(f(i) = f(i-1) + f(i-2)\)。
另外，需要注意处理余数问题。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-11 19:24:20
*/
public int countHousePlacements(int n) {
long a = 1, b = 2;
long cnt = b;
for (int i = 2; i <= n; i++) {
cnt = (a + b) % 1_000_000_007;
a = b;
b = cnt;
}
return (int) ((cnt * cnt) % 1_000_000_007);
}