2320：统计放置房子的方式数（1607 分）

力扣第 299 场周赛第 2 题

题目

一条街道上共有 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

相似问题：

• 0070：爬楼梯
• 0198：打家劫舍

分析

• 两侧独立，只用统计一侧，再平方即可
• 按最后一个位置放不放即可递推

解答

1
2
3
4
5
6
7

lass Solution:
    def countHousePlacements(self, n: int) -> int:
        mod = 10**9+7
        a,b = 1,1
        for _ in range(n):
            a,b = b,(a+b)%mod
        return b*b%mod

68 ms