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

🎯 问题描述（来源于LeetCode）

描述：
给定一个长度为 n 的街道，街道两侧都有一排相同数量的地块。每侧的地块编号从 1 到 n。
你可以在每个地块上放置房子，但同一侧相邻地块不能同时放置房子（即不能有相邻的房子）。
两侧的放置是独立的，问有多少种放置方案。答案对 10^9+7 取模。

说明：

  • 两侧可以放置不同数量的房子。
  • 同一侧不能出现相邻的房子（类似打家劫舍的约束）。

示例：

  • 示例 1：
1
2
3
输入: n = 1
输出: 4
解释: 每侧有2种方案（放或不放），总方案数为 2*2=4。
  • 示例 2：
1
2
3
输入: n = 2
输出: 9
解释: 每侧方案数为3（00,01,10），总方案数 3*3=9。

💻 解题思路

思路：动态规划（斐波那契） + 独立乘法定理

算法步骤

  1. 先考虑单侧：在长度为 n 的一排地块上，不能放置相邻的房子，问有多少种放置方案。
    这等价于经典的“房屋染色”问题，方案数满足斐波那契递推：
    • 设 dp[i] 表示前 i 个地块的方案数。
    • 若第 i 块不放房子，则方案数为 dp[i-1]。
    • 若第 i 块放房子，则第 i-1 块不能放，方案数为 dp[i-2]。
    • 边界：dp[0]=1（空地），dp[1]=2（放或不放）。
    • 因此 dp[i] = dp[i-1] + dp[i-2]，即为斐波那契数列。
  2. 用户代码使用滚动变量 a, b 迭代计算，得到 dp[n] 的值存储在 b 中。
  3. 由于两侧独立，总方案数为 (b * b) % MOD。

代码实现

1
2
3
4
5
6
7
8
9
class Solution:
    def countHousePlacements(self, n: int) -> int:
        MOD = 10**9 + 7
        # 单侧方案数：dp[0]=1, dp[1]=2, dp[i]=dp[i-1]+dp[i-2]
        a, b = 1, 2  # a = dp[0], b = dp[1]
        for _ in range(2, n + 1):
            a, b = b, (a + b) % MOD
        # 两侧独立，总方案数为 b^2
        return (b * b) % MOD

📊 性能分析

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(1)O(1)

思考

本题本质是求斐波那契数列，并利用乘法原理。用户代码简洁高效，利用了滚动变量避免了数组开销。注意：dp[0]=1 对应没有地块时只有一种方案（不放任何房子）。当 n=1 时，dp[1]=2，平方得 4，正确。这是 LeetCode 2320 的标准解法。