C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

DP 括号序列

想要让一个括号序列合法有两个条件：

条件1：左括号数和右括号数相同
条件2：任意前缀序列中左括号数不小于右括号数


闫氏DP分析法：

            集合：只考虑前i个括号左比右多j的集合
状态表示：
            条件：数量


状态计算：  0           1           2       ···         j+1

        f[i-1][j+1]   f[i-1][j]   f[i-1][j-1]          f[i-1][0]

状态转移方程：f[i][j] = f[i-1][j+1] + f[i-1][j] + ··· + f[i-1][0]
              f[i-1][j] + ··· + f[i-1][0] = f[i][j-1]

        = >   f[i][j] = f[i-1][j+1] + f[i][j-1]

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

const int N = 5010, MOD = 1e9 + 7;
typedef long long ll;

int n;
char str[N];
ll f[N][N];

ll calc() {
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int i = 1; i <= n; i ++)
        if (str[i] == '(') {
            for (int j = 1; j <= n; j ++)
                f[i][j] = f[i - 1][j - 1];
        }
        else {
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;
            for (int j = 1; j <= n; j ++)
                f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % MOD;
        }
    for (int i = 0; i <= n; i ++)    
        if (f[n][i])
            return f[n][i];
    return -1;        
}

int main() {
    cin >> str + 1;
    n = strlen(str + 1);

    ll l = calc();

    reverse(str + 1, str + n + 1);
    for (int i = 1; i <= n; i ++)
        if (str[i] == '(') str[i] = ')';
        else str[i] = '(';
    ll r = calc();
    cout << l * r % MOD;
    return 0;
}