[数据结构与算法]括号序列【第十二届】【省赛】【B组】 DP

思路

设$dp[i][j]$表示到第$i$个括号，当左括号比右括号多$j$个的情况下，添加左括号的方案数。首先显然在一堆左括号里添加左括号对方案数是毫无贡献的，因此只有在一堆右括号中加左括号才会对方案产生贡献。则：

• s[i] == '('时，$dp[i][j]=dp[i?1][j?1]$；
• s[i] == ')'时，$dp[i][j]=dp[i?1][j+1]+dp[i?1][j]+dp[i?1][j?1]+?+dp[i?1][2]+dp[i?1][1]$

什么意思？

对于当前$i$括号为右括号，左括号比右括号多$j$的情况而言，其状态由 不加(加零个)左括号的方案数(也就是左括号比右括号多$j+1$个的方案数)、加一个左括号的方案数(左括号比右括号多$j$个的方案数)、…相加得到

但是这样复杂度会跑到$O(n^3)$，显然跑不动，那么考虑优化：

容易发现右括号时候的式子类似斐波那契的式子，可以改为递推式：
$$\begin{gathered} dp[i][j]=dp[i?1][j+1]+dp[i?1][j]+dp[i?1][j?1]+?+dp[i?1][2]+dp[i?1][1]+dp[i?1][0] \\ dp[i][j?1]=dp[i?1][j]+dp[i?1][j?1]+?+dp[i?1][2]+dp[i?1][1]+dp[i?1][0] \\ \to dp[i][j]=dp[i?1][j+1]+dp[i][j?1] \end{gathered}$$
优化完毕！

Accepted Code

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

const int N = 5010, MOD = 1e9 + 7;
int dp[N][N];

inline int calc(string s){
    int len = s.size();
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for(int i = 1; i <= len; i++){
        if(s[i - 1] == '(') for(int j = 1; j <= len; j++) dp[i][j] = dp[i - 1][j - 1];
        else{
            dp[i][0] = (dp[i - 1][1] + dp[i - 1][0]) % MOD;
            for(int j = 1; j <= len; j++) dp[i][j] = (dp[i - 1][j + 1] + dp[i][j - 1]) % MOD;
        }
    }
    for(int i = 0; i <= len; i++) if(dp[len][i]) return dp[len][i];
    return -1;  
}

inline void solve(){
    string s; cin >> s;
    string ss = s;
    reverse(ss.begin(), ss.end());
    for(int i = 0; i < ss.size(); i++) ss[i] = (ss[i] == '(') ? ')' : '(';
    cout << calc(s) * calc(ss) % MOD << endl;
}

signed main(){
    solve();
    return 0;
}