2222. 选择建筑的方案数

发表于 分类于 阅读次数： Waline： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

  • 状态机DP
  • 状态压缩

思路

从三维 DP 到五变量状态压缩的完整推导

给定一个仅由 '0' 与 '1' 组成的字符串，要求统计所有满足模式： \[ 010 \quad \text{或} \quad 101 \] 的 长度为 3 的子序列 的总数量。

一、第一次 AC 解法：显式 DP（分层子序列计数）

1. 状态定义

设字符串长度为 \(n\)，定义： \[ f[k][i] = \text{以位置 } i \text{ 结尾的长度为 } k \text{ 的合法子序列个数} \] 其中：

  • \(k = 1\)：单个字符
  • \(k = 2\)：合法两位模式 01 或 10
  • \(k = 3\)：目标模式 010 或 101

数组维度为： \[ f[1..3][1..n] \]

2. 初始值设计（第一次代码的关键点）

1
2
for (int i = 1; i <= s.size(); ++i)
    f[1][i] = 1;

含义是： \[ f[1][i] = 1 \quad \forall i \] 即：

每一个位置自身都能形成一个长度为 1 的子序列。

这是后续构造长度为 2、3 的计数基底。

3. 状态转移方程（统一形式）

对于任意 \(k \in \{2,3\}\)，维护两个前缀累加器：

  • \(a\)：前缀中，所有“末位为 0 的 \(k-1\) 长度子序列个数”
  • \(b\)：前缀中，所有“末位为 1 的 \(k-1\) 长度子序列个数”

遍历字符串： \[ \text{当前字符 } s[i] = \begin{cases} 0: & f[k][i] += b,\quad a \mathrel{+}= f[k-1][i] \\ 1: & f[k][i] += a,\quad b \mathrel{+}= f[k-1][i] \end{cases} \] 含义为：

  • 当前是 0，只能由之前的 1 结尾的子序列转移过来
  • 当前是 1，只能由之前的 0 结尾的子序列转移过来

4. 结果统计

1
2
for (int i = 1; i <= n; ++i)
    res += f[3][i];

即： \[ \text{答案} = \sum_{i=1}^{n} f[3][i] \]

5. 时间与空间复杂度

  • 时间复杂度： \[ O(3n) = O(n) \]

  • 空间复杂度： \[ O(3n) \]

该解法逻辑清晰，但由于使用了二维大数组 + 两层循环，常数较大。

6. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    static const int maxn = 1e5 + 5;
    long long numberOfWays(string s) {
        long long f[4][maxn];
        int n = s.size();
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= s.size(); ++i)
            f[1][i] = 1;
        for (int k = 2; k <= 3; ++k) {
            long long a = 0, b = 0;
            for (int i = 1; i <= s.size(); ++i) {
                if (s[i - 1] == '0')
                    f[k][i] += b, a += f[k - 1][i];
                else
                    f[k][i] += a, b += f[k - 1][i];
            }
        }
        long long res = 0;
        for (int i = 1; i <= s.size(); ++i)
            res += f[3][i];
        return res;
    }
};

二、第二次 AC 解法：状态压缩（五变量线性统计）

核心思想是： 把 DP 过程中的“所有前缀统计量”直接压缩为常数个变量。

1. 状态变量定义

1
long long cnt0, cnt1, cnt01, cnt10, res;

对应数学含义：

变量 含义
\(cnt0\) 当前前缀中 0 的个数
\(cnt1\) 当前前缀中 1 的个数
\(cnt01\) 当前前缀中子序列 "01" 的个数
\(cnt10\) 当前前缀中子序列 "10" 的个数
\(res\) 最终答案，等于 "010" 与 "101" 总数

2. 初始值设计（与第一份 DP 的对应关系）

1
cnt0 = cnt1 = cnt01 = cnt10 = res = 0;

对应到第一次 DP：

  • 等价于所有 f[2][*]、f[3][*] 初始均为 0

  • 所有统计完全由扫描过程中“在线累加”获得

  • cnt0、cnt1 在扫描中隐式等价于第一次解法中： \[ a = \sum f[1 \text{ 且以 } 0 \text{ 结尾}],\quad b = \sum f[1 \text{ 且以 } 1 \text{ 结尾}] \]

3. 状态转移（实质为第一次 DP 的“展开形态”）

遍历每一个字符：

若当前字符为 '0'

1
2
3
cnt10 += cnt1;   // 新的 "10"
res += cnt01;    // 新的 "010"
++cnt0;

对应数学形式： \[ \begin{aligned} cnt10 &\leftarrow cnt10 + cnt1 \\ res &\leftarrow res + cnt01 \\ cnt0 &\leftarrow cnt0 + 1 \end{aligned} \]

若当前字符为 '1'

1
2
3
cnt01 += cnt0;   // 新的 "01"
res += cnt10;    // 新的 "101"
++cnt1;

即： \[ \begin{aligned} cnt01 &\leftarrow cnt01 + cnt0 \\ res &\leftarrow res + cnt10 \\ cnt1 &\leftarrow cnt1 + 1 \end{aligned} \]

4. 与第一次 DP 的一一对应关系

第一次 DP 含义 第二次压缩变量
a (前缀 0 结尾长度1) cnt0
b (前缀 1 结尾长度1) cnt1
f[2] 中以 01 结尾的数量 cnt01
f[2] 中以 10 结尾的数量 cnt10
f[3] 总和 res

因此：

第二份代码不是“新算法”，而是把第一次 DP 的三层结构 完全展开成常数个在线累加器。

5. 复杂度对比

解法 时间复杂度 空间复杂度 说明
显式 DP（第一次） \(O(n)\) \(O(n)\) 结构直观，但有数组
状态压缩（第二次） \(O(n)\) \(O(1)\) 等价逻辑，常数最优

6. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    long long numberOfWays(string s) {
        long long cnt0 = 0, cnt1 = 0, cnt01 = 0, cnt10 = 0, res = 0;
        for (char& chr : s) {
            if (chr == '0')
                cnt10 += cnt1, res += cnt01, ++cnt0;
            else
                cnt01 += cnt0, res += cnt10, ++cnt1;
        }
        return res;
    }
};

三、核心结论

  1. 两份代码在数学上是完全等价的
  2. 第一次是「层级 DP 建模」
  3. 第二次是「将 DP 状态全部投影为前缀计数变量」
  4. 真正的提速来源是：
    • 消除二维数组访问
    • 消除第三层循环
    • 全程使用寄存器级变量