题目来自蓝桥杯练习系统

代码链接：https://blog.csdn.net/yanweiqi1754989931/article/details/123093179

这一题在思路不清楚的情况下相当难理解和解决，包括代码，解的话一开始笔者就没什么思路，想出来的方案要么超时要么难以操作

附上代码和解析的思路，希望能帮到和笔者一样被严重困扰的朋友

#include <bits/stdc++.h>
#define int long long
using namespace std;
// 最大长度和模 
const int N = 5010, MOD = 1e9 + 7;
// dp[i][j]代表到第i个符号， 左括号比右括号多i个的添加方案(添加的是左括号) 
int dp[N][N];

inline int calc(string s) {
//    长度
    int len = s.size();
//   初始化
    memset(dp, 0, sizeof dp);
//  读到位置为0时左括号比右括号多0个的解决方案数量为1
    dp[0][0] = 1;
// 依次枚举每个位置 
    for(int i = 1; i <= len; i++) {
// i-1转换为索引 
        if(s[i - 1] == '(') {
            
//            依次左比右多1~len个的情况 
            for(int j = 1; j <= len; j++) {
//                继承上一个的状态，因为读入的是左括号，所以不能加左括号了 
                dp[i][j] = dp[i - 1][j - 1];
            }
        } else {

//            这里处理了j=0的情况，即右括号大于等于左括号时方案数为上一个 相同情况下的方案数和左括号多一个的状态（补全当前的右括号） 
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
//            如果为右括号,考虑添加左括号，那方案就是之前情况的基础上(j-1的情况，相当于少一个的情况已经考虑了)和，和上一个阶段多一个左括号的情况（多一个左括号，因为没有给出顺序，所以认为是弥补了此次的右括号）         
            for(int j = 1; j <= len; j++) {
                dp[i][j] = (dp[i - 1][j + 1] + dp[i][j - 1]) % MOD;
            }
        }
    }
    
//    调试的输出 
    cout<<s<<endl;
    cout<<"j: ";
    for(int j=0;j<=len;j++){
        printf("%4lld ",j);
    }
    cout<<endl; 
    for(int i = 0; i <= len; i++) {
        cout<<i<<": ";
        for(int j = 0; j <= len; j++) {
            printf("%4lld ",dp[i][j]);
        }
        cout<<endl; 
    }


    for(int i = 0; i <= len; i++) {
//    返回第一个不为零的值，理论上不可能是无解的，为什么取第一个不为0的是因为 存在((((这种情况
// dp4 0 的值为0的，也就是不能再加左括号了 
        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] == '(') ?  ')' : '(';
    }
//    最终解为两种情况乘积对mod取模 ：ss其实是s的镜像比如s:(((),ss:)(((->)))(
// 乘积的原理：形如)(((,此时必然要添加一个左括号以补全左边的右括号，只有一种补全方案，所以1*，而添加右括号的方式有5种，所以是5*
// 所需要添加的左右括号方案便是1*5 
    cout << calc(s) * calc(ss) % MOD << endl;
}

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