G7024 [GESP202609 七级] 括号序列 题解

知识点：动态规划、括号序列、计数。

解题思路

DP以未匹配左括号数为状态，每个字符可跳过；选择左括号使余额加1，选择右括号仅在余额正时减1。最终dp[0]是答案。

为什么正确

合法括号序列等价于任何前缀余额非负且最终为0，逐字符两类选择一一对应原下标子序列，状态限制正好筛出合法者。

易错点

空子序列也合法，初始dp[0]=1；按下标区分相同字符串，模数为10^9而非10^9+7。

复杂度

时间O(n²)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin>>n>>s;
    vector<long long>dp(n+2);
    dp[0]=1;
    for(char c:s) {
        auto ndp=dp;
        for(int j=0;j<=n;j++)if(c=='(')ndp[j+1]=(ndp[j+1]+dp[j])%1000000000;
        else if(j)ndp[j-1]=(ndp[j-1]+dp[j])%1000000000;
        dp.swap(ndp);
    }
    cout<<dp[0];
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。