题目描述

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

题解——找规律+递推

图片

思路

类似于上台阶,找到递推关系即可

记录上一个位置放置和不放置的方法数,不相临可以解释为上一个位置不放,这一个位置才能放,所以下一个位置放置的方法数就是上一个不放置的方法数,而不放置的方法数就是上一个位置的所有方法数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int countHousePlacements(int n) {
        long yes=1,no=1,mod=1e9+7;//yes记录放置的方法数,no记录不放置的
        for(int i=2;i<=n;++i)
        {
            int temp=yes;//保存temp
            yes=no%mod;//这个位置放置的方法为上一个位置不放的方法
            no=(no+temp)%mod;//不放的方法是上一次的所有方法
        }
        return (yes+no)*(yes+no)%mod;
    }
};