蓝桥杯每日一题：括号序列

啊哈哈哈！?很有难度的一道题呀@—@

题目?

【问题描述】

给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。

两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。

例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和 ((()))。

【输入格式】

输入一行包含一个字符串 s ，表示给定的括号序列，序列中只有左括号和右括号。

【输出格式】

输出一个整数表示答案，答案可能很大，请输出答案除以 1000000007 (即10e9+7) 的余数。

【测试样例1】

Input：

((()

Output：

5

【评测用例规模与约定】

对于 40% 的评测用例，∣s∣≤200。

对于所有评测用例，1≤∣s∣≤5000。

解析

这道题呢就是一个括号匹配的问题，其实这种题目也是非常经典的一类题目。

因为我们刚开始认识栈的时候，都会举括号匹配的例子来说明栈的应用。

这种括号的题目是必须遵守一个规则的：

在任何时候，一个合法的括号序列都满足左括 号的数量大于等于右括号的数量！

? 举一个例子：

• ()))这个括号序列在 i=2，3 的时候都是不合法的（下标从 0 开 始计数），
• 而((()这个括号序列在当前都是合法的，

这是因为：

? ? ? ?左括号匹配右括号， 如果只有右括号没有与之对应的左括号的话就必须得在这个右括号之前加上一 个左括号。

? ? ? ? 而如果左括号比右括号多的话，在这个位置之后可能还会有右括号和 前面的左括号对应，所以我们不一定非得在这个时候加上右括号。

那么解决这个题目的算法是什么呢？

这道题存在大量的重叠子问题，如果 dfs 一个个求的话，我们的时间复杂度会很高，再来看看我们的数据范围 1≤|s| ≤5000，也就是我们必须得设计一个 O（n^2）以内的算法才能通过所有的测试 用例，所以这道题可以使用动态规划来解决。

我们该如何定义状态？

我们可以先看左括号，用 f[i][j]来表示我们遍历 到第 i 个括号，此时左括号比右括号多 j 个的时候的添加括号方案数。

先算出 添加左括号的方案数，再从右到左算出添加右括号的方案数，最后两个相乘就是 我们的结果。

其实对于这道题来说，我们不需要写两个函数分别求左括号和右括号方案数， 我们可以先算出左括号方案数，然后把这个字符串进行翻转，然后将左括号换成 右括号，右括号换成左括号再求一次这个函数就是右括号的方案数。

这是为什么呢？

我们可以倒着看一下，上面的定理对于倒着依旧是相对成立的，倒着看的 时候，一个合法的括号序列都满足右括号的数量大于等于左括号的数量。具体可 以把上面的论点逆着推一下。

可能会有人有疑问，为什么两个方案数是相乘的关系，对于两个括号中间加 入左右括号，难道里面的括号重新排列不是另一种方案吗？

其实他们之间是相对 独立的，我们可以这样想，

…… |……

如果我们在 | 的地方加入一个左括号， 一个右括号的话，只能形成 ) ( 这样的序列，不能形成这样()，这是因为如果是 后者的话，这算一对括号，可以抵消掉，还多了一对，题目的要求是尽可能少地 添加若干括号，所以无论怎样，都只会有一种排列方式。

既然这样的话，我们怎么保证添加的时候不重复呢？

也就是(((我们算成了好 几种，其实只有一种。我们可以以右括号为界限，如果以右括号为界限，比如这 样……）……）……，其实……都是左括号，他们无论怎样排列都是一样的。

至此我们的状态转移方程就好写了，我们只考虑在右括号的前面添加 n 个左 括号，因为其他时候添加左括号其实都一样(里面全是左括号的话怎么排列都是 一样的)。

• 当我们遇到左括号的时候非常简单，直接把这个左括号加进来，就是 比前一个状态多了 1 个左括号，f[i][j]=f[i-1][j-1]。比如我们前面左括号比右括号 多 5 个，那么现在我们遇到的是左括号,我们的左括号就比右括号多了 6 个。
• 当我们遇到的是右括号的时候，我们考虑在右括号前面添加 n 个左括号，从 0 开始枚举，我们前面加 0 个左括号就是 f[i][j]=f[i-1][j+1]，因为前面左括号比右 括号多 j+1 个，现在遇到右括号了，我们不加左括号的情况下就多了 j 个。如果 加 1 个左括号的话 f[i][j]=f[i-1][j]，因为前面左括号比右括号多 j 个，现在遇到右 括号了，我们加 1 个左括号的情况下就多了 j 个，以此类推。

所 以 f[i][j] 就 是 前 面 添 加 左 括 号 的 所 有 情 况 相 加 ， 即 f[i][j]=f[i-1][j+1]+f[i-1][j]+f[i-1][j-1]+……+f[i-1][0]。

我们会发现，如果这样子加的话 我们时间复杂度就是 O(n)，会使得整体时间复杂度变成 O(n^3)会超时。 不过我们可以发现 f[i][j-1]=f[i-1][j]+f[i-1][j]+f[i-1][j-1]+……+f[i-1][0]，这样的话 f[i][j]=f[i-1][j+1]+f[i][j-1]就会是 O(1)的时间复杂度了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5005;
int f[N][N];
int mod=1e9+7;
string s;
int n;
LL get(){
//memset 函数是内存赋值函数，用来给某一块内存空间进行赋值的；包含
//在<string.h>头文件中,可以用它对一片内存空间逐字节进行初始化；
//原型为 ：void *memset(void *s, int v, size_t n);
 memset(f,0,sizeof f);
 f[0][0]=1;
 //就是 f[0][0]=1，即我们看到前 0 个括号，左括号比右括号多 0 个的方案数
//为 1，也是符合实际的。
 //注意在遇到右括号的时候我们要特别处理一下 f[i][0]，这是因为根据上面
//的状态转移方程，当 j=0 时 f[i][j-1]会越界，
//我们就用上面 O(n)的方法对 f[i][0]进行特殊处理，因为只有两项，所以也是
O(1)的时间复杂度。
 for(int i=1;i<=n;i++){
 if(s[i-1]=='('){
 for(int j=1;j<=n;j++)
 f[i][j]=f[i-1][j-1];
 }
 else{
 f[i][0]=(f[i-1][1]+f[i-1][0])%mod;
 for(int j=1;j<=n;j++)
 f[i][j]=(f[i-1][j+1]+f[i][j-1])%mod;
 }
 }
 for(int i=0;i<=n;i++)
 if(f[n][i])
 return f[n][i];
 return -1;
}
int main(){
 cin>>s;
 n=s.size();
 LL x=get();
 //头文件 “algorithm”,将容器[first, last )范围内的元素颠倒顺序放置。
 reverse(s.begin(),s.end());
 for(int i=0;i<n;i++){
 if(s[i]==')')
 s[i]='(';
 else
 s[i]=')';
 }
 LL y=get();
 cout<<(x*y)%mod
}

?