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

发表于 分类于 阅读次数： Waline： 本文字数： 633 阅读时长 ≈ 2 分钟

考点

  • 线性DP

思路

一、问题抽象与建模

题目描述了一条街道，两侧各有 \(n\) 个地块。在每个地块上可以选择是否建房，但同一侧不能出现相邻的两栋房子。要求统计所有合法放置方案的数量，结果对 \(10^9+7\) 取模。

问题的关键在于以下两个观察：

  1. 街道左右两侧互不影响 左侧地块的放置情况不会对右侧产生任何约束，反之亦然。
  2. 单侧问题是一个经典的一维相邻约束问题 对于一条长度为 \(n\) 的线段，每个位置可以选择放或不放，但不能出现连续两个“放”。

因此，原问题可以拆解为：

先计算单侧的合法方案数，再将其平方。

二、单侧问题的动态规划设计

1. 状态定义

考虑街道的一侧，共有 \(n\) 个位置。

定义：

  • \(dp_0(i)\)：前 \(i\) 个位置中，第 \(i\) 个位置不放房子的方案数
  • \(dp_1(i)\)：前 \(i\) 个位置中，第 \(i\) 个位置放房子的方案数

2. 状态转移

根据相邻不能同时放房的约束：

  • 若第 \(i\) 个位置不放房子，则第 \(i-1\) 个位置可以放或不放： \[ dp_0(i) = dp_0(i-1) + dp_1(i-1) \]

  • 若第 \(i\) 个位置放房子，则第 \(i-1\) 个位置必须不放： \[ dp_1(i) = dp_0(i-1) \]

于是，单侧在前 \(i\) 个位置上的总方案数为： \[ g(i) = dp_0(i) + dp_1(i) \]

三、化简为斐波那契型递推

将上面的转移关系合并，可以直接得到： \[ \begin{aligned} g(i) &= dp_0(i) + dp_1(i) \\ &= (dp_0(i-1) + dp_1(i-1)) + dp_0(i-1) \\ &= g(i-1) + g(i-2) \end{aligned} \] 因此，单侧方案数满足斐波那契型递推： \[ \begin{cases} g(0) = 1 & \text{（空街道）} \\ g(1) = 2 & \text{（放 / 不放）} \\ g(i) = g(i-1) + g(i-2) & i \ge 2 \end{cases} \]

四、合并左右两侧

由于左右两侧完全独立，总方案数为： \[ \text{Answer} = g(n)^2 \bmod (10^9 + 7) \]

五、算法复杂度分析

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(1)\)（仅使用滚动变量）

六、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    static const int mod = 1e9 + 7;

    int countHousePlacements(int n) {
        // p2 = g(i-2), p1 = g(i-1)
        long long p2 = 1; // g(0) = 1
        long long p1 = 2; // g(1) = 2
        long long c;

        // 计算单侧的斐波那契型递推
        for (int i = 2; i <= n; ++i) {
            c = (p1 + p2) % mod; // g(i) = g(i-1) + g(i-2)
            p2 = p1;
            p1 = c;
        }

        // 左右两侧独立，总方案数为平方
        return p1 * p1 % mod;
    }
};