LeetCode讲解篇之2320. 统计放置房子的方式数
文章目录
- 题目描述
- 题解思路
- 题解代码
- 题目链接
题目描述
题解思路
我们首先发现一个规律街道两侧是否放置房子是独立的，即放置房子的方式数 = 一侧放置房子的方式数 * 另一侧放置房子的方案数 = 一侧放置房子的方式数的二次方
对于一侧[0, i]范围内地块放置房子的方式数为第i号地块不放房子的方式数 + 第i号地块放房子的方式数
设一侧[0, i]范围内地块放置房子的方式数为f[i]
则f[i] = f[i - 1] + f[i - 2]
第i号地块不放房子的方式数为[0, i - 1]范围内放置房子的方式数
第i号地块放房子的方式数为[0, i - 2]范围内放置房子的方式数
题解代码
func countHousePlacements(n int) int {
const mod = 1e9 + 7
f := make([]int, n + 1)
f[0], f[1] = 1, 2
for i := 2; i <= n; i++ {
f[i] = (f[i - 1] + f[i - 2]) % mod
}
return f[n] * f[n] % mod
}
题目链接
https://leetcode.cn/problems/count-number-of-ways-to-place-houses/