2466. 统计构造好字符串的方案数

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

考点

  • 线性DP

思路

一、问题描述（抽象化）

给定四个整数：

  • low、high：字符串长度的合法区间
  • zero：一次可以追加的 '0' 的个数
  • one ：一次可以追加的 '1' 的个数

从空字符串开始，每一步可以选择：

  • 追加 zero 个 '0'
  • 或追加 one 个 '1'

字符串的构造顺序不同视为不同方案。

目标是：

统计所有最终长度在区间 \([low,,high]\) 内的字符串构造方案数，对 \(10^9+7\) 取模。

二、问题建模（状态压缩思想）

1. 核心观察

  • 字符串的具体内容不重要
  • 只关心当前字符串长度
  • 每次操作仅影响「长度」，且步长固定为 zero 或 one

因此，该问题可以抽象为：

从长度 \(0\) 出发，每次向右走 zero 或 one 步， 统计能到达区间 \([low,,high]\) 内各长度的路径总数。

这本质上是一个：

  • 一维状态
  • 完全背包
  • 排列型动态规划问题

三、状态定义

定义一维 DP 数组： \[ f[i] = \text{构造出长度恰好为 } i \text{ 的好字符串方案数} \]

四、初始条件（Base Case）

空字符串是唯一的起点： \[ f[0] = 1 \] 表示：

构造长度为 0 的字符串，有且只有 1 种方式（什么都不做）。

其余状态初始为 0。

五、状态转移方程

对于任意 \(i \ge 1\)，若当前长度 \(i\) 可由之前的状态转移而来：

  • 如果 \(i \ge zero\)，可以从 \(i - zero\) 追加 zero 个 '0'
  • 如果 \(i \ge one\)，可以从 \(i - one\) 追加 one 个 '1'

则有转移方程： \[ f[i] = \begin{cases} f[i - zero] + f[i - one], & i \ge \max(zero, one) \\ f[i - zero], & zero \le i < one \\ f[i - one], & one \le i < zero \\ 0, & i < \min(zero, one) \end{cases} \] 实现时可统一写为： \[ f[i] = \begin{cases} 0, & i < \min(zero, one) \\ (f[i - zero] \text{ if } i \ge zero) + (f[i - one] \text{ if } i \ge one), & \text{otherwise} \end{cases} \] 每一步对 \(10^9 + 7\) 取模。

六、答案的构成方式

题目要求统计的是：

最终长度在区间 \([low,,high]\) 内的所有方案

因此最终答案为： \[ \text{ans} = \sum_{i=low}^{high} f[i] \pmod{10^9+7} \] 这一步并非技巧，而是题意的直接体现。

七、算法复杂度分析

  • 时间复杂度： \[ O(high) \]

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

使用一维 DP，空间已最优。

八、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    static const int maxn = 1e5 + 5, mod = 1e9 + 7;
    int countGoodStrings(int low, int high, int zero, int one) {
        long long f[maxn] = {};
        long long res = 0;
        f[0] = 1;
        for (int i = min(zero, one); i <= high; ++i) {
            if (i >= zero)
                f[i] = (f[i] + f[i - zero]) % mod;
            if (i >= one)
                f[i] = (f[i] + f[i - one]) % mod;
            if (i >= low)
                res = (res + f[i]) % mod;
        }
        return res;
    }
};