【CDOJ 1321】柱爷的恋爱
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn=300+7;
const int mod=1000000007;
int n;
string s;
long long int dp[maxn][maxn];
bool match(int l,int r) //匹配括号
{
if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))
return true;
return false;
}
long long int dfs(int l,int r)
{
if(~dp[l][r]) return dp[l][r];
long long int &ans=dp[l][r]=0;
if(l>r) return ans=1;
if(l==r) return ans=1;
ans=dfs(l+1,r); //删除括号
ans%=mod;
for(int i=l;i<=r;i++){ //枚举配对
if(match(l,i)){
ans+=dfs(l+1,i-1)*dfs(i+1,r);
ans%=mod;
}
}
return ans%mod;
}
int main()
{
scanf("%d",&n);
cin>>s;
memset(dp,-1,sizeof(dp));
long long int ans=(dfs(0,n-1)-1)%mod;
printf("%lld",ans);
return 0;
}