题目描述
括号序列
样例
略
算法1
(DP+多重背包化简) $O(n^2)$
首先:明确括号合法得条件,第一,左右括号数量要想等,第二,任意前缀的左括号数量要不小于右括号数量(可以这样理解,我们后面还要添加右括号,所以在添加左括号的时候,只要数量不小于右括号即可合法,枚举所有的情况,最后取刚好合法的时候即可)
其次,明确方案数量的计算,左右括号可以单独计算、单独添加,因为左右括号添加的顺序并无影响且我们不可能同时添加一对括号,没有意义,因为这两个添加到同一个空隙的顺序就只有方向相悖,即左括号添加在右括号之前,右括号添加在左括号之前,所以单独计算即可。
最后,在进行右括号计算时,只需将源字符串逆置且取反即可,在进行dp总结时,f[i][j]表示只考虑前i个括号,左括号比右括号多j的方案的集合,就要分析当前枚举到的i是右括号还是左括号,如果是左括号,要想满足条件,前一种状态一定是f[i-1][j-1]那么j可以取1–n,否则,要分析前一种状态添加了多少左括号,j取0–j+1,方案数相加组成前一种状态的集合。
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>//首先找到合法的条件
using namespace std;//第一,左右括号数量相同,第二,任意前缀中,左括号数目不小于右括号数目
const int N=5010;//且左右括号可单独添加单独计算方案数
const int MOD=1e9+7;//由于如果左右括号添加在同一空隙中,只有一种顺序,只能相悖方向,否则是多余的,不满足尽可能的少
typedef long long int ll;
ll f[N][N];//只考虑前i个括号,左比右多j的方案数量集合
char s[N];
int n;
ll cal()
{
memset(f,0,sizeof f);//初始化集合为空
f[0][0]=1;//没有字符的时候,只有一种方案
for(int i=1;i<=n;i++)//枚举每一个符号
{
if(s[i]=='(')//如果当前括号是左括号,则上一个状态只能是j-1
{
for(int j=1;j<=n;j++) //枚举每一个j,j最多是n,如果字符串全是左括号
f[i][j]=f[i-1][j-1];
}
else//如果遇到的是右括号,前一种可能已经添加了0---j+1个左括号,迭加
{//f[i][j]=f[i-1][j+1]+f[i-1][j]+f[i-1][j-1].......+f[i-1][0];(1)
//f[i][j-1]=f[i-1][j]+f[i-1][j-1]+....+f[i-1][0];(2)
f[i][0]=(f[i-1][1]+f[i-1][0])%MOD;//特判0,防止数组越界
for(int j=1;j<=n;j++)
{
f[i][j]=(f[i-1][j+1]+f[i][j-1])%MOD;//综合(1)(2)得
}
}
}
for(int i=0;i<=n;i++)//问的是至少,从小到大枚举,看方案数是否存在
{
if(f[n][i])
return f[n][i];
}
return -1;
}
int main()
{
cin>>s+1;//字符数组以1开始
n=strlen(s+1);
ll sum1=cal();//计算左括号的方案数
reverse(s+1,s+n+1);//将字符串倒置
for(int i=1;i<=n;i++)//且将左括号变成右括号,右括号变成左括号
{
if(s[i]=='(')
s[i]=')';
else
s[i]='(';
}
ll sum2=cal();//再次计算左括号,此时的左括号相当于原来的右括号
cout<<(sum1*sum2)%MOD;//方案数相乘
return 0;
}