括号序列问题，往往就是把左括号看成+1，右括号看成-1，我们只需要保证任意一个前缀大于等于0，且总和为0，就代表是个合法括号序列了。
令(f[i][j])表示当前到第(i)个字符，现在的前缀和(j)。那么分三种情况考虑。
若第(i+1)个字符是左括号，则能转移到(f[i+1][j+1])。
若第(i+1)个字符是右括号，则能转移到(f[i+1][j-1])。
若第(i+1)个字符是问号，则能转移到(f[i+1][j-1])与(f[i+1][j+1])。
最终(f[n][0])就是方案总数啦。
时间复杂度为(O(n^2))。
优化：
二维数组一定会炸。。。。
那就。。。循环队列！
我们发现每次到新的一个 $i $，它只和 (i-1) 有关，所以 (i-1) 用过一次就可以销毁了，不然也是占空间
可以像这样&1来实现循环利用
f[i & 1][0]=0
STD
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int n;
int f[3005][3005];
char c[3005];
int main()
{
scanf("%d",&n);
scanf("%s",c+1);
f[0][0]=1;
for(int i=1;i<=n;i++)
{
if(c[i]=='Y')
{
for(int j=1;j<=i;j++)
{
f[i][j]=f[i-1][j-1];
}
}
if(c[i]=='H')
{
for(int j=0;j<i;j++)
{
f[i][j]=f[i-1][j+1];
}
}
if(c[i]=='C')
{
f[i][0]=f[i-1][1];
for(int j=1;j<i;j++)
{
f[i][j]=(f[i-1][j+1]+f[i-1][j-1])%mod;
}
f[i][i]=f[i-1][i-1];
}
}
cout<<f[n][0]%mod;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int n;
int f[3][10005];
char c[10005];
int main()
{
freopen("data10.in","r",stdin);
freopen("data10.out","w",stdout);
scanf("%d",&n);
scanf("%s",c+1);
memset(f,0,sizeof(f));
f[0][0]=1;
for(int i=1;i<=n;i++)
{
if(c[i]=='Y')
{
f[i&1][0]=0;
for(int j=1;j<=i;j++)
{
f[i&1][j]=f[(i-1)&1][j-1];
}
}
if(c[i]=='H')
{
f[i&1][i]=0;
for(int j=0;j<i;j++)
{
f[i&1][j]=f[(i-1)&1][j+1];
}
}
if(c[i]=='C')
{
f[i&1][0]=f[(i-1)&1][1];
for(int j=1;j<i;j++)
{
f[i&1][j]=(f[(i-1)&1][j+1]+f[(i-1)&1][j-1])%mod;
}
f[i&1][i]=f[(i-1)&1][i-1];
}
}
cout<<f[n&1][0]%mod;
}