题解 | #合法的括号序列#

首先看数据量2000，可以开二维的2000，考虑动态规划.dp[i][j]表示前i个字符中，没有配对的左括号数量。

动态转移方程：

如果第i个字符为左括号'('：那么只能从前一个i-1状态的j个没有配对的左括号转移过来(多了一个没有配对的左括号)，dp[i][j+1]=dp[i-1][j];

如果第i个字符为右括号')'：那么也只能从前一个i-1状态j个没有配对的左括号转移过来(少了一个没有配对的左括号)dp[i][j-1]=dp[i-1][j];

如果第i个字符为问号'?'：那么它可以是左括号也可以是右括号，所有上面的两种转移方式都可以。dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];

最终输出dp[n][0]即可。

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=2004;
int dp[maxn][maxn];
int main() {
    string str;
    cin>>str;
    int n=str.size();
    str="1"+str;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        if(str[i]=='('){
            for(int j=0;j<=i;j++){
                dp[i][j+1]=(dp[i][j+1]+dp[i-1][j])%mod;                
            }
        }else if(str[i]==')'){
            for(int j=1;j<=i;j++){                
                dp[i][j-1]=(dp[i][j-1]+dp[i-1][j])%mod;
            }
        }else {
            for(int j=0;j<=i;j++){
                dp[i][j+1]=(dp[i][j+1]+dp[i-1][j])%mod;                
            }
            for(int j=1;j<=i;j++){                
                dp[i][j-1]=(dp[i][j-1]+dp[i-1][j])%mod;
            }
        }
    }
    cout<<dp[n][0]<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")