1，问题描述
2320. 统计放置房子的方式数
难度：中等
一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。
现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。
注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。
示例 1：
1
2
3
4
5
6
7
8
| 输入：n = 1
输出：4
解释：
可能的放置方式：
1. 所有地块都不放置房子。
2. 一所房子放在街道的某一侧。
3. 一所房子放在街道的另一侧。
4. 放置两所房子，街道两侧各放置一所。
|
示例 2：
1
2
3
| 输入：n = 2
输出：9
解释：如上图所示，共有 9 种可能的放置方式。
|
提示：
2，初步思考
我最初理解成为01背包方案个数的问题，使用动态规划解决也正常完成
但是看完题解才反应过来是斐波那契数列
3，代码处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| package questions;
import java.util.Arrays;
public class _2320统计放置房子的方式数 {
static final int MOD = (int) 1e9 + 7, MX = (int) 1e4 + 1;
static final int[] f = new int[MX];
static {
f[0] = 1;
f[1] = 2;
for (var i = 2; i < MX; ++i)
f[i] = (f[i - 1] + f[i - 2]) % MOD;
}
public int countHousePlacements_fib(int n) {
return (int) ((long) f[n] * f[n] % MOD);
}
public int countHousePlacements(int n) {
int[][] dp = new int[n + 1][2];
Arrays.fill(dp[1], 1);
for (int i = 2; i <= n; i++) {
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % 1000000007;
dp[i][1] = dp[i - 1][0];
}
long res = 0;
res += dp[n][0] % 1000000007;
res += dp[n][1] % 1000000007;
return (int)((long) res *res % 1000000007);
}
public static void main(String[] args) {
_2320统计放置房子的方式数 countHousePlacements = new _2320统计放置房子的方式数();
System.out.println(countHousePlacements.countHousePlacements(1000));
}
}
|