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

我们假设 dp[i][j] 代表在当前位 i 之前，还有 j 个左括号的情况的数量，那么很明显，初始情况下 dp[0][0]=1

如果第 i 位是可以是一个左括号，那么代表对于所有的 dp[i-1][x] ，都可以让 dp[i][x+1] 增加其权值也就是 dp[i-1][x]，因为这个左括号会拼接在之前的所有情况下，使得这个新情况多了一个左括号 x+1

如果第 i 位是可以是一个右括号，那么代表对于所有的 x 不等于0的情况 dp[i-1][x] ，都可以让 dp[i][x-1] 增加其权值也就是 dp[i-1][x]，因为这个右括号会和之前的一个左括号匹配，少了一个左括号 x-1

然后我们发现这里 dp 数组只涉及相邻项的转移，所以 i 这一维根本不用，只用一个dp[j]数组即可

然后给大家一个个人经验，对于这种只转移有效状态的 dp 数组来说，我们最好使用map来维护，复杂度会更加优秀，例如初始状态下，只存在一个有效状态就是 dp[0]=1，那么我就没有必要遍历0到2000来更新下一维护的dp数组，因为其最多只会更新出一个新状态就是 dp[1]

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int __t = 1, n;
string s;
void solve() {
    cin >> s;
    map<int, int> dp;
    dp[0] = 1;
    for (auto c : s) {
        map<int, int> ndp;
        if (c == '(' || c == '?')
            for (auto [k, v] : dp)
                ndp[k + 1] = (ndp[k + 1] + v) % mod;
        if (c == ')' || c == '?')
            for (auto [k, v] : dp)
                if (k)
                    ndp[k - 1] = (ndp[k - 1] + v) % mod;
        dp = ndp;
    }
    cout << dp[0] << '\n';
    return;
}
int32_t main() {
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    // cin >> __t;
    while (__t--)
        solve();
    return 0;
}