2320. 统计放置房子的方式数

Difficulty
Medium
Tags
动态规划
URL
https://leetcode.cn/problems/count-number-of-ways-to-place-houses/
Star
一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。
现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。
注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。
示例 1：
输入：n = 1
输出：4
解释：
可能的放置方式：
1. 所有地块都不放置房子。
2. 一所房子放在街道的某一侧。
3. 一所房子放在街道的另一侧。
4. 放置两所房子，街道两侧各放置一所。
示例 2：
notion imagenotion image
输入：n = 2
输出：9
解释：如上图所示，共有 9 种可能的放置方式。
提示：
  • 1 <= n <= 104
通过次数3,130提交次数9,953

法1 动态规划

思路
类似
🖼️
198. 打家劫舍 ，本题同样思路即可。然后道路两边的地块是独立的，最后只需要平方即可。
题解
class Solution:
    def countHousePlacements(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        # dp[i][0] 以i结尾的地块不放房子
        # dp[i][1] 以i结尾的地块修房子
        
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = 1
        dp[0][1] = 1

        for i in range(1, n):
            dp[i][0] = dp[i-1][0] + dp[i-1][1]
            dp[i][1] = dp[i-1][0]

        return ((sum(dp[-1]) % MOD) ** 2) % MOD