题解#2

分析

问题：统计字符串$S$（只含 ( 和 ) ）的所有子序列中，合法括号序列的数量（含空串），答案对$10^9$取模。$n \le 2000$。
关键观察：一个子序列是合法括号序列，当且仅当：
1.
长度是偶数$2k$
2.
前$k$个字符全是 ( ，后$k$个全是 )
DP 设计：设$f[i][j]$表示考虑前$i$个字符，当前已选子序列中有$j$个未匹配的 ( 的方案数。

不选 $S[i]$：$f[i][j] \mathrel{+}= f[i-1][j]$

选 $S[i]$：

若$S[i] = ( ：f[i][j] \mathrel{+}= f[i-1][j-1]$（多了一个未匹配左括号）

若$S[i] = ) ：f[i][j] \mathrel{+}= f[i-1][j+1]$（匹配掉一个左括号）
最终答案为$f[n][0]$（所有左括号都被匹配）。
验证：$S = ))(()($

空串：1 种

() ：选位置$3,4$或$3,6$，共 2 种

总计 3 $✓$
复杂度：$O(n^2)$，$n \le 2000$完全可行。

代码：

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9;
const int MAXN = 2005;

int n;
char s[MAXN];
long long f[2][MAXN];  // 滚动数组

int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);

    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int cur = i & 1, pre = cur ^ 1;
        for (int j = 0; j <= n; j++) f[cur][j] = 0;
        for (int j = 0; j <= i; j++) {
            // 不选 s[i]
            f[cur][j] = (f[cur][j] + f[pre][j]) % MOD;
            // 选 s[i]
            if (s[i] == '(') {
                if (j >= 1) f[cur][j] = (f[cur][j] + f[pre][j - 1]) % MOD;
            } else {
                if (j + 1 <= i) f[cur][j] = (f[cur][j] + f[pre][j + 1]) % MOD;
            }
        }
    }

    printf("%lld\n", f[n & 1][0]);
    return 0;
}

验证：

样例1：$))(()($，答案$f[6][0] = 3 ✓$

样例2：34 个字符，17 个 ( 后 17 个 ) ，答案$333606220$（可用代码验证）
说明：

$f[i][j]$中$j$最大为$i$（前$i$个字符最多选$i$个左括号），内层循环到$i$即可

用滚动数组将空间从$O(n^2)$降到$O(n)$

答案包含空串（$f[0][0] = 1$的转移路径）