题目链接:
本题和198.打家劫舍有异曲同工之妙。
由于街道两侧互不干扰,因此可以考虑只计算出一侧的状态,然后利用乘法原理即可。
状态划分时,考虑第 \(i\) 个地块选或不选:
- 若选,则第 \(i-1\) 个地块不能选,第 \(i - 2\) 个地块可选可不选。\(f[i]=f[i-2]\)
- 若不选,则第 \(i-1\) 个地块可选可不选,\(f[i]=f[i-1]\)。
class Solution {
public:
int countHousePlacements(int n) {
const int MOD = 1e9 + 7;
vector<int> f(n + 1);//f[i]表示街道的一侧前i个地块放置房屋的方案数
f[0] = 1;//空着,一种方案
f[1] = 2;//空或不空,两种方案
for (int i = 2; i <= n; i++) {
f[i] = (f[i - 1] + f[i - 2]) % MOD;
}
return (long long)f[n] * f[n] % MOD;//注意这里f[n]*f[n]可能会溢出,需要用long long隐式转换一下
}
};
标签:方案,2320,地块,int,房子,放置,一侧
From: https://www.cnblogs.com/pangyou3s/p/18137084