dp[j] = 选出子序列后当前平衡数为 j 的方案数(过程中平衡数始终 ≥ 0),答案取 dp[0]。
题目来源:[GESP202609 七级] 括号序列(洛谷 P17460)。
对于字符串 S 与 T,如果从 S 中删除任意多个字符可以得到 T,那么 T 是 S 的子序列。换言之,T 是选取 S 中的若干字符按下标顺序连接而成的。两个子序列不同,当且仅当所选取的下标不同。
例如 sequence 有 2⁸ 个不同的子序列,其中有三个不同的子序列 e,因为它的第 2、5、8 个字符都是 e,分别保留这三个字符得到的子序列被视为不同。
对于字符串 S,如果满足以下条件,则称它是合法括号序列:S 是空字符串;或 S 可由 (、一个合法括号序列、) 三者连接得到;或 S 可由两个合法括号序列连接得到。
输入格式:第一行一个正整数 n,表示 S 的长度;第二行一个长度为 n、仅包含 ( 与 ) 的字符串 S。
输出格式:一行一个整数,表示 S 的合法括号子序列数量对 10⁹ 取模的结果。
例如 S 为 ))(()( 时共有 3 个子序列是合法括号序列:空字符串,以及两个不同的子序列 ()。
1 ≤ n ≤ 2000;40% 的数据 n ≤ 400。
( 的个数不少于 ),且整体两者数量相等。用"平衡数"(( 记 +1、) 记 −1 的前缀和)说就是:过程中平衡数始终 ≥ 0,最后恰好等于 0。子序列计数括号匹配平衡数(前缀和)方案数 DP前缀非负模 10⁹
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行长度为 n 的字符串 S |
| 输出 | 合法括号子序列数量对 10⁹ 取模的结果 |
| 数据范围 | 1 ≤ n ≤ 2000(40% 数据 n ≤ 400) |
| 字符集 | 只有 ( 与 ) |
| 子序列约定 | 按下标选取,下标集合不同即算不同 |
| 合法定义 | 空串;( + 合法 + );两个合法串连接 |
( 比 ) 多多少"——也就是当前平衡数。不需要记住整个串,所以状态用一个整数就够)( 这样的串,最终"数量是相等的"(平衡数为 0),但第一段就成了负平衡的非法前缀。只看总数不看守恒非负,就会把 )( 错算成合法))(()( 里的两个 () 要算 2 次。方案数 DP 每选一次字符就累加一次,天然满足这个要求dp[0] 的初值 1 就代表它,最后直接用 dp[0] 就是答案,不用加不用减先把 6 个字符的下标与内容列清楚,再一步步跑 DP。
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 字符 | ) | ) | ( | ( | ) | ( |
| 合法子序列 | 能怎么选 | 个数 |
|---|---|---|
| 空串 | 一个字符都不选 | 1 |
() | 取下标 3 的 ( 与下标 5 的 ) | 1 |
() | 取下标 4 的 ( 与下标 5 的 ) | 1 |
| 长度为 4 或 6 的串 | 左侧的 ( 只有下标 3、4、6,凑不出"先左后右"的更长结构 | 0 |
总计 3 ✓
| 步骤 | 当前字符 | dp[0] | dp[1] | dp[2] | dp[3] | 这一步怎么来的 |
|---|---|---|---|---|---|---|
| 初始 | — | 1 | 0 | 0 | 0 | 空子序列:平衡数 0 有 1 种 |
| 1 | ) | 1 | 0 | 0 | 0 | 这个 ) 只能"不选":选了平衡数变 −1,非法 |
| 2 | ) | 1 | 0 | 0 | 0 | 同上,仍然是只能不选 |
| 3 | ( | 1 | 1 | 0 | 0 | dp[1] = dp[1] + dp[0] = 0 + 1 |
| 4 | ( | 1 | 2 | 1 | 0 | dp[1] = 1 + 1 = 2;dp[2] = 0 + 1 = 1 |
| 5 | ) | 3 | 3 | 1 | 0 | dp[0] = dp[0] + dp[1] = 1 + 2 = 3;dp[1] = 2 + 1 = 3 |
| 6 | ( | 3 | 6 | 4 | 1 | dp[0] 不变;dp[1] = 3 + 3 = 6;dp[2] = 1 + 3 = 4;dp[3] = 0 + 1 = 1 |
))为什么 dp[0] 变成 3新 dp[0] = 老 dp[0](不选这个 ))+ 老 dp[1](选这个 ))
= 1 + 2 = 3
含义:平衡数仍是 0 的方案有 3 种 —— "空串" + "两个不同的 ()"
✅ 正好对上手工枚举
()dp[1] 变成 6新 dp[1] = 老 dp[1](不选)+ 老 dp[0](选)
= 3 + 3 = 6
这个 ( 是下标 6,而它后面已经没有任何字符可以用来配对
所以它只会让"平衡数 1"的方案变多,不会改变 dp[0]
✅ 答案仍是 dp[0] = 3
( 时新状态从 dp[j−1] 转移来(平衡数 +1);遇到 ) 时新状态从 dp[j+1] 转移来(平衡数 −1)。dp[j] 原样保留——这正是"每个字符都有选 / 不选两条岔路"的体现,也是 2ⁿ 个子序列的由来。( 接 17 个 ),答案 333606220样例 2 的 S 是 17 个 ( 后面紧跟 17 个 ),n = 34。这一组可以用组合恒等式独立算出来,正好用来交叉检验我们的 DP。
所有 ( 都在前 17 位,所有 ) 都在后 17 位
任取 i 个 ( 与 i 个 ),按下标拼出来必然是"i 个左 + i 个右"
这种串的前缀左括号数从头到尾都不少于右括号数,且总数相等
所以它一定合法;反之合法的也必然是这样取出来的
合法子序列数 = Σ C(17,i) · C(17,i)(i = 0 ~ 17,i = 0 就是空串)
Σ C(n,i)² = C(2n, n)
所以 Σ(i = 0 ~ 17) C(17,i)² = C(34,17)
C(34,17) = 2333606220
✅ 精确值 2333606220
2333606220 mod 1000000000 = 333606220
与样例输出完全一致
这也说明 DP 的取模必须每一步都做,否则 n = 2000 时早就溢出了
✅ 333606220
DP 结果 333606220 ✓
333606220,多半是犯了两个经典错误之一——dp[0] 的初值写成 0,或最后手动减了 1);10⁹ + 7)。dp[j] = 当前平衡数为 j 的方案数;每个字符"选 / 不选"两条转移
枚举每一个下标选取方案,逐个判断是否合法
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 平衡数 DP(正解) | O(n²) ≈ 4 × 10⁶ | 约 20 行 |
| 枚举 2ⁿ 个子序列 | 2²⁰⁰⁰ | ❌ 不可行 |
| 组合闭式公式 | 仅"全 ( 接全 )"这类特殊结构成立 | ❌ 一般的 S 无闭式 |
第一行输入 n,第二行输入只含 ( 与 ) 的字符串。程序用平衡数 DP 计数,规模较小时还会显示逐字符的 dp 表并做暴力核对。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000000; // 注意是 10⁹,不是 10⁹ + 7 int n; char S[2005]; long long dp[2005], ndp[2005]; int main() { scanf("%d", &n); scanf("%s", S + 1); // 下标从 1 开始,方便书写 dp[0] = 1; // 空子序列:平衡数为 0,方案数 1 for (int i = 1; i <= n; i++) { for (int j = 0; j <= n; j++) // 情况一:不选第 i 个字符 ndp[j] = dp[j]; if (S[i] == '(') { for (int j = 1; j <= n; j++) // 情况二:选它,平衡数 +1 ndp[j] = (ndp[j] + dp[j - 1]) % MOD; } else { for (int j = 0; j <= n; j++) // 情况二:选它,平衡数 −1 ndp[j] = (ndp[j] + dp[j + 1]) % MOD; } for (int j = 0; j <= n; j++) // 滚动:把新状态交给下一轮 dp[j] = ndp[j]; } printf("%lld\n", dp[0]); // dp[0] 里已经包含空子序列 return 0; }
j ≥ 0 上进行:选 ( 时从 dp[j−1] 累加,选 ) 时从 dp[j+1] 累加。)"而当前平衡数已经是 0,它只会去读 dp[1] 之类的状态,永远不会产生"平衡数为 −1"的方案——非法前缀在状态层面就被彻底排除了。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
dp[0] = 1 | 初值 | 空子序列平衡数为 0,算 1 种方案;这也是空串被计入的地方 |
ndp[j] = dp[j] | 不选 | 当前字符不进子序列,平衡数不变,方案数原样继承 |
( 时 ndp[j] += dp[j−1] | 选 ( | 选一个左括号,平衡数从 j−1 涨到 j,所以从前一档累加 |
) 时 ndp[j] += dp[j+1] | 选 ) | 选一个右括号,平衡数从 j+1 降到 j,所以从后一档累加 |
dp / ndp 轮换 | 滚动数组 | 每轮只依赖上一轮,空间从 O(n²) 压到 O(n) |
% 1000000000 | 取模 | 每步都取,防止 n = 2000 时数值溢出;常量是 10⁹ |
printf("%lld", dp[0]) | 答案 | 平衡数 0 且全程非负 ⟺ 合法括号序列 |
j − 1 < 0 的越界访问),会把 )( 这类串算成合法;② 去重(用 set<string> 收集字符串),题目要求"下标不同即不同",去重必然少算;③ 取模常量写错(本题是 10⁹,不是常见的 10⁹ + 7);④ 数组开小:转移会访问到 dp[n],数组至少要开到 n + 1。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
6 | 3 | 题面样例 1 |
34 | 333606220 | 题面样例 2:等于 C(34,17) mod 10⁹ |
1 | 1 | 只有空串合法(单个左括号配不成对) |
1 | 1 | 右括号永远开不了头,同样只剩空串 |
2 | 1 | 「)(」不是合法括号序列 —— 这就是"过程中必须非负"的典型 |
2 | 2 | 空串 + 唯一的「()」 |
3 | 3 | 两个不同下标的「()」要分别计数,加空串共 3 |
4 | 1 | 全是左括号,凑不出右括号,只剩空串 |
4 | 6 | 空串 1 + 长度为 2 的「()」4 个 + 「(())」1 个 = 6 |
( 从 j−1、) 从 j+1)?② 空串算进去了吗(dp[0] 初值为 1)?③ 每步都 mod 10⁹ 吗?④ 拿 17 个 ( + 17 个 ) 验一下,输出是不是 333606220?)(、)(() 这类串也算进去。在 DP 里只要坚持"转移只在 j ≥ 0 上进行",这条约束就自动成立。))(()( 里两个不同的 () 要算 2 个;用 set 去重会少算。dp[0] 的初值 1 已经把它算进去了,最后不要再额外加 1 或减 1。dp[n](选 ) 时从 dp[j+1] 取),数组长度至少 n + 1。只需要两个长度为 n + 1 的数组 dp、ndp。因为每轮只依赖上一轮的结果,用滚动数组把本可以 O(n²) 的状态压到了 O(n)。
✅ 约 400 万次操作,1 秒时限内轻松通过。对比暴力枚举的 2²⁰⁰⁰——一次 DP 就把"指数级"压成了"平方级",这就是动态规划最迷人的地方。
// ① 平衡数 DP 的骨架(会了这一个,改几行就能解一串变体) dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= n; j++) ndp[j] = dp[j]; // 不选第 i 个字符 if (S[i] == '(') for (int j = 1; j <= n; j++) ndp[j] = (ndp[j] + dp[j-1]) % MOD; else for (int j = 0; j <= n; j++) ndp[j] = (ndp[j] + dp[j+1]) % MOD; for (int j = 0; j <= n; j++) dp[j] = ndp[j]; // 滚动 } printf("%lld\n", dp[0]); // ② 判断"一个给定括号串"本身是否合法(计数器写法,与栈等价) int bal = 0; bool ok = true; for (char c : s) { bal += (c == '(' ? 1 : -1); if (bal < 0) { ok = false; break; } // 前缀为负 → 非法 } if (ok && bal == 0) puts("YES"); else puts("NO"); // ③ 只要"最长合法子序列长度",把存方案数改成存长度 // dp2[j] = 平衡数为 j 时的最大长度(-inf 表示不可达),最后 dp2[0] 即答案 // ④ 再加一维 k 表示"恰好选了 k 个左括号",就变成 O(n²k) 的加强版
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 平衡数(前缀和) | 把"括号是否匹配"浓缩成一个整数 | 括号匹配、正则括号、栈模拟、括号树 |
| 按"变化量"设状态 | dp[j] 只记当前平衡数,不记整串 | 序列类 DP、状态压缩、LIS 的滚动优化 |
| 计数型 DP | 统计方案数而不是最优值 | 组合计数、路径计数、子序列计数 |
| 滚动数组 | dp / ndp 交替,空间从 O(n²) 到 O(n) | 所有"只依赖上一层"的 DP |
| 每步取模 | 防止大数溢出、保证结果正确 | 所有"答案对 X 取模"的计数题 |
dp[j] 里存的值从"方案数"换成"最大长度",不可达记成 −∞,答案取 dp[0];② 再加一维 k,变成 dp[j][k],复杂度 O(n²k)。