DP
状态定义
f[i][j]表示前i个括号中左括号比右括号多几个
状态转移
- 如果当前是左括号:f[i][j] = f[i-1][j-1]
- 如果当前是右括号:f[i][j] = f[i-1][j+1] + f[i][j-1]
解释
如果当前是右括号,那么可以选择在该右括号前面插入0-j+1个左括号,表示为:
f[i][j] = f[i-1][j+1] + f[i-1][j] + f[i-1][j-1] + … + f[i-1][0]
至于为什么是j+1,是因为当前是右括号,相当于抵消了一个左括号。
这个公式除去第一项,后面的就表示f[i][j-1],所以最终的状态转移方程为:
f[i][j] = f[i-1][j+1] + f[i][j-1]
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9+7;
const int maxn = 5005;
int f[maxn][maxn];
string s;
int cal() {
int cnt = 0;
memset (f, 0, sizeof f);
int len = s.size();
f[0][0] = 1;
for (int i = 0; i < len; i++) {
if (s[i] == '(') {
for (int j = 1; j <= len; j++) {
f[i+1][j] = f[i][j-1];
}
} else {
f[i+1][0] = (f[i][1] + f[i][0]) % mod;
for (int j = 1; j <= len; j++) {
f[i+1][j] = (f[i][j+1] + f[i+1][j-1]) % mod;
}
}
}
for (int i = 0; i <= len; i++) {
if (f[len][i]) return f[len][i];
}
return -1;
}
signed main() {
cin >> s;
int len = s.size();
int l = cal();
reverse(s.begin(), s.end());
for (int i = 0; i < len; i++) {
if (s[i] == '(') s[i] = ')';
else s[i] = '(';
}
int r = cal();
//cout << l << " " << r << "\n";
cout << l*r%mod << "\n";
}