括号序列 第12届蓝桥杯省赛c++b组 J题 满分题解

备赛2022年class="superseo">蓝桥杯，这道题我只能写出dfs代码，得15分
然后看了多篇博客题解和讲解视频，但一直没看懂题解…
本来这次是想直接放弃，
最终硬着头皮想通了。
所以我想分享自己在看的过程中产生的问题，以及这些问题的答案。

题目要求输出有多少种本质不同的添加结果。在笔者这里，将题目要求输出的结果称为为总方案数。题解中给出了总方案数的计算方法。
总方案数=添加左括号的方案数*添加右括号的方案数
我看题解的时候，这里产生了三个问题。
1.为什么总方案数=添加左括号的方案数*添加右括号的方案数？
2.添加的左括号的方案数是多少，怎么算？
3.添加的右括号的方案数是多少，怎么算？
在我继续学习的过程中我寻找这三个问题的答案，在寻找答案的过程中又产生了新的问题，经过不断的自顶向下式的学习，了解到这个问题的核心是括号序列的合规性的定义，只有明白括号序列的合规性，才能知道添加左括号的方案数的含义，以及理解计算左括号方案数的方法。知道了左括号的计算方法就能知道添加的右括号的方案数的计算方法，他们的计算方法是一样的。得出了左右括号的方案数，就得到了题目的答案。

注：这里的括号序列合规不等于题目中说的括号序列合法。
该题括号合规性定义：如果该括号序列的每一子段以及本身都满足左括号的数量大于等于右括号的数量，那这个括号序列是合规的。
这里需要解释清楚 括号序列的每一子段 的含义。我们以’)‘为隔板，两个’)‘之间的内容加上右侧的’)‘就是该括号序列的一个子段。
为了帮助大家理解子段定义，举几个例子。
例子1：((() 这个括号序列只有一个子段，即他的本身((() 。
例子2：() 这个括号序列也只有一个子段，即他的本身()。
例子3：( 这个括号序列没有子段。因为序列中没有’)‘。
例子4：)())))( 这个括号序列有五个子段，分别是),(),),),)。虽然该括号序列最后的’)‘后还有一个’(‘，但是单独的一个’('不是括号序列的子段。
为了帮助大家理解括号序列合规性定义，举几个例子。
例子1：((() 这个括号序列只有一个子段，且该子段有三个左括号，一个右括号，因为左括号的数量大于等于右括号的数量，所以是一个合规的括号序列。
例子2：() 这个括号序列只有一个子段，且该子段有一个左括号，一个右括号，因为左括号的数量等于右括号的数量，所以也是一个合规的括号序列。
例子3：( 这个括号序列没有子段，即该序列的子段为空，他的本身只有一个左括号，0个有括号，故也是一个合规的括号序列。
例子4：)())))( 这个括号序列有五个子段，分别是),(),),),)，除第二个子段合规，其他的四个子段都不合规。故该括号序列不合规。
括号合规性的意义：上面花费大篇幅介绍了括号合法性的定义，因为他有着重要的意义，理解括号合规性，是理解动态规划递推关系式的前提条件。
括号合规性的意义是如果该括号序列合规，那就不需要给该括号序列添加左括号，如果括号不合规，需要添加左括号，使得括号序列合规，即向每个不合法的括号序列子段添加左括号，使得每个括号序列子段合规。
下面举例解释：
例子1：((() 括号序列合规，不需要添加左括号。
例子2：())) 括号序列不合规，需要添加至少两个左括号才能使该括号序列合规。
例子3：)())))( 这个括号序列有五个子段，分别是),(),),),)，除第二个子段合规，其他的四个子段都不合规。故该括号序列需要添加至少四个左括号使得该括号序列合规。

总方案数：即题目要求输出的答案
添加左括号的方案数，再从右到左算出添加右括号的方案数，最后两个相乘就是我们的结果，即总方案数=添加左括号的方案数*添加右括号的方案数。

添加左括号的方案数：即尽可能少的添加左括号使得该括号序列合规，且添加的位置必须在添加完成后，会产生不同的添加结果，有多少种本质不同的添加结果就有多少种方案数。
举个例子帮助理解：
例子1：())) 该括号序列不合规，需要至少添加两个左括号，会产生5种不同的结果((())),(()()),()()(),()(()),(())(),故添加左括号的方案数是5种。
例子2：)())))( 这个括号序列有五个子段，分别是),(),),),)，需要至少添加四个左括号，会产生28种不同的结果。故添加左括号的方案数是28种。
由例子2看出，随着括号序列的增长，方案数也是爆炸性的增加，所以我们需要一种好的方法来进行计算。
题解中用动态规划方法进行计算，计算的速度非常快，而且代码行数也很少。不过笔者在看题解的过程中，看不懂动态规划转移方程，也不懂动态规划数组中每个数字的含义。经过反复思考终于理解了题解的算法，下面结合着例子1与例子2来讲解。
dp[i][j]含义
笔者用dp[i][j]来表示状态，dp[i][j]表示我们遍历到第 i 个括号，此时左括号比右括号多 j 个的时候的添加括号方案数。注意，这里提到的添加括号方案数不同于上面提到的添加左括号的方案数。其中括号序列的下标i从1开始，如例子1())) 的dp[1][1]=1代表遍历到第一个括号，产生的括号序列为‘(’，在该括号序列‘(’中左括号比右括号多1个的时候的添加括号方案数只有一种，就是添加0个左括号。
笔者在这里进行详细的解释添加括号方案数的含义，添加括号方案数是指在只能添加左括号且左括号只能添加在原括号序列中右括号的左侧，在添加了n个括号后（n>=0），产生了多少种本质不同的合规结果就有多少种方案数。

例子1())) 的dp[2][1]=1代表遍历到第二个括号‘)’，产生的括号序列为‘()’，在该括号序列‘()’中左括号比右括号多1个的时候的添加括号方案数只有一种，就是添加1个左括号。添加的位置如下图所示

可以看到，添加了左括号后，新的括号序列‘(()’中左括号比右括号多1个，满足要求。
例子1())) 的dp[2][2]=1代表遍历到第二个括号‘)’，产生的括号序列为‘()’，在该括号序列‘()’中左括号比右括号多2个的时候的添加括号方案数只有一种，就是添加2个左括号。添加的位置如下图所示

大家理解了dp[i][j]的含义就可以学习动态转移方程了。下面是题解建立的动态转移方程：

当第i个括号是'('时
dp[i][j] = dp[i-1][j-1];
当第i个括号是')'时
dp[i][j] = dp[i-1][0] + dp[i-1][1] + … + dp[i-1][j] + dp[i-1][j+1];
	当地i个括号是')'时，且i大于1时
	dp[i][j] = dp[i-1][j+1] + dp[i][j-1]
i : 遍历到第 i 个括号
j : 此时左括号比右括号多 j 个

在解释动态转移方程前，我们需要明白dp的初试状态。
以例子1())) 解释
dp的初试状态dp[0][0]=1 ，dp[0][1]=0，dp[0][2]=0 … dp[0][j+1]=0。
在这里需要解释为什么dp[0][0]=1 ，dp[0][1]=0，dp[0][2]=0…，以及dp数组有多少行与多少列。
dp[0][0]=1表示括号序列为空（0个左括号0个右括号），且左括号比右括号多0个的时候的添加括号方案数只有一种，就是添加0个左括号。
dp[0][1]=0表示括号序列为空（0个左括号0个右括号），且左括号比右括号多1个的时候的添加括号方案数有0种。**根据添加括号方案数的含义：在只能添加左括号且左括号只能添加在原括号序列中右括号的左侧，在添加了n个括号后（n>=0），产生了多少种本质不同的合规结果就有多少种方案数。**因为空序列没有右括号，所以没有添加左括号的位置，故无法添加左括号，故空序列不存在左括号比右括号多1个的时候，所以就不存在添加括号的方案。dp[0][2]=0 … dp[0][j+1]=0同理。
我们来逐行解释建立的动态转移方程。
当第i个括号是’('时，dp[i][j] = dp[i-1][j-1]
dp[i-1][j-1]=x表示由前i-1个括号构成的序列，通过添加左括号，使得左括号比右括号多j-1个的时候的添加括号方案数有x种。每一个方案对应这一个新序列，当我们直接把这个左括号（第i个括号）加到新序列最右边，就是比前一个状态多了1个左括号，前一个状态左括号比右括号多j-1个，加入了一个左括号后，新状态左括号比右括号多j个。故前i-1个括号构成的序列，通过添加左括号，使得左括号比右括号多j-1个的时候产生的本质不同的合规结果数 与 前i个括号构成的序列，通过添加左括号，使得左括号比右括号多j个的时候产生的本质不同的合规结果数相同。
推理的话说的比较繁琐，下面举个例子帮助大家理解上述的话。
设括号序列为‘)(’,很明显dp[1][2]=1，因为dp[1][2]代表遍历到第一个括号‘)’，产生的括号序列为‘)’，在该括号序列‘)’中左括号比右括号多2个的时候的添加括号方案数只有一种，就是添加3个左括号。添加3个左括号产生的新括号序列为((()。而dp[2][3]=dp[1][2]=1,因为dp[2][3]代表遍历到第二个括号‘)(’，产生的括号序列为‘)(’，在该括号序列‘)(’中左括号比右括号多3个的时候的添加括号方案数只有一种，就是添加3个左括号。添加3个左括号产生的新括号序列为((()(。两者只有一点区别，就是最右侧差一个’(‘。
通过上面的例子大家应该可以推广到dp[i][j]，不管i多大，前i个序列与前i-1个序列他们产生的新括号序列只有一点区别，就是最右侧差一个’('，所以他们产生的本质不同的合规结果数相同，故dp[i][j] = dp[i-1][j-1]。
笔者接着解释下一个动态规划方程， 笔者卡在这个动态规划方程好几天，觉得这是这份题解最难理解的部分了。
当第i个括号是’)'时，dp[i][j] = dp[i-1][0] + dp[i-1][1] + … + dp[i-1][j] + dp[i-1][j+1];

解释：dp[i][j]=x表示遍历到第i个括号，产生的括号序列为前i个括号构成的序列，要通过添加左括号得到新序列，新序列满足左括号比右括号多j个，且有x种新序列。
这些新序列可以由
前i-1个字符的序列左括号比右括号多0个的情况，再在这个右括号（第i个括号）相邻的左侧加j+1个左括号得到
前i-1个字符的序列左括号比右括号多1个的情况，再在这个右括号（第i个括号）相邻的左侧加j个左括号得到
.
.
.
前i-1个字符的序列左括号比右括号多j+1个的情况，再在这个右括号（第i个括号）相邻的左侧加0个左括号得到
我们还是来看个例子，帮助理解这段话的意义。
设括号序列为‘))’,dp[2][2]=4 ,对应4种新序列，分别是()((()，(()(()，((()()，(((())
其中dp[1][0]+dp[1][1]+dp[1][2]+dp[1][3]=4
dp[1][0]=1代表遍历到第一个括号，产生的括号序列为)，需要添加一个左括号，产生的新序列()左括号比右括号多0个。
dp[2][2]代表遍历到第二个括号，产生的括号序列为))，当在第i个括号‘)’相邻的左侧加3个左括号，若要满足要求，需要继续添加一个左括号，而添加左括号的方案数与dp[1][0]一样，都在最左侧添加一个左括号，产生的新序列的为()((()，可以看到加粗的部分就是dp[1][0]对应的新序列。
dp[1][1]=1代表遍历到第一个括号，产生的括号序列为)，需要添加两个左括号，产生的新序列(()左括号比右括号多1个。
dp[2][2]，当在第i个括号‘)’相邻的左侧加2个左括号，若要满足要求，需要继续添加两个左括号，而添加左括号的方案数与dp[1][1]一样，且新序列(()(()的加粗部分的就是dp[1][1]对应的新序列。
dp[1][2]=1代表遍历到第一个括号，产生的括号序列为)，需要添加三个左括号，产生的新序列((()左括号比右括号多2个。
dp[2][2]，当在第i个括号‘)’相邻的左侧加1个左括号，若要满足要求，需要继续添加三个左括号，而添加左括号的方案数与dp[1][2]一样，且新序列((()()的加粗部分的就是dp[1][2]对应的新序列。
dp[1][3]=1代表遍历到第一个括号，产生的括号序列为)，需要添加四个左括号，产生的新序列(((()左括号比右括号多3个。
dp[2][2]，当在第i个括号‘)’相邻的左侧加0个左括号，若要满足要求，需要继续添加四个左括号，而添加左括号的方案数与dp[1][3]一样，且新序列(((())的加粗部分的就是dp[1][3]对应的新序列。
我们接着解释下一个方程
当地i个括号是’)'时，且i大于1时 dp[i][j] = dp[i-1][j+1] + dp[i][j-1]
这是单纯的数学推理，
因为dp[i][j-1] = dp[i-1][0] + dp[i-1][1] + … dp[i-1][j]，
所以 dp[i][j] = dp[i][j-1]+dp[i-1][j+1] 。
到此，动态规划方程的内容全部讲完。这时大家还要记得我们构建动态规划方程的目的，我们的目的是求添加左括号的方案数。设该括号序列有len位（下标从1开始）其中有a个左括号b个右括号，且至少添加x个左括号才能合规，根据dp[i][j]的含义与添加左括号的方案数定义，我们可以推出，dp[len][a+x-b]=添加左括号的方案数定义。那我们要怎么知道x是几呢？答案是我们不需要知道x是几，因为在不知道x的值也能求出结果。
这里可能有些难懂，笔者来给大家解释。首先求x比较麻烦，我们有更方便的方法，所以不需要求写专门的算法求x，只需要遍历第len行，从左向右遍历，第一个不为零的数就是我们要找的dp[len][a+x-b]。代码如下

for(int i=0;i<=len;i++)//len是括号序列的长度
        if(dp[len][i]!=0)
        	return dp[len][i];
        return -1;

因为至少要添加x个左括号才能合规，所以当i 4.计算添加右括号的方案数

计算添加右括号的方案数的方法是把括号序列进行翻转，然后将左括号换成右括号，右括号换成左括号，这时计算添加右括号的方案数就变成了计算添加左括号的方案数，按照求左括号方案数的方法再求一次就是右括号的方案数。之所以能这样，是因为括号序列的添加右括号的方式与添加左括号的方式是对称的，是镜像关系的，在添加右括号时需要从右往左看，这与添加左括号从左往右看是完全对称的，故添加右括号产生的序列 与 该括号序列翻转且转换后在对称的位置上添加左括号产生的序列是一一对应的。这种一一对应的关系决定了两者的方案数相等。
还是举个例子帮助理解
设括号序列为)(()(，现在要添加右括号使其匹配。匹配的意思与上文说的合规类似，只是把左括号换成了右括号，从左向右改为从右向左。括号序列)(()(要添加右括号的位置如下图所示

对括号序列)(()(进行翻转与左右括号的转化，可以得到该序列)())(。该序列)())(要添加左括号的位置如下图所示

若在序列)(()(最右侧添加一个右括号，与序列)())(最左侧添加一个左括号对应，如同镜子的两面。故序列)(()(添加右括号的方案数，等同于序列)())(添加左括号的方案数。

当我们为原序列添加左括号与右括号时是相互独立的，添加的左括号不会影响右括号的添加，因为他们添加的位置不重叠。且添加的左括号也不会提供新的位置给右括号添加，因为在添加的左括号的相邻右边添加右括号会形成这样()，这样会抵消添加的左右括号。题目的要求是尽可能少地添加若干括号，如果形成这样()，就多添加了两个括号，不符合题意。
所以总方案数=添加左括号的方案数*添加右括号的方案数
还是举个例子，说明左右括号的添加互不干扰。
设括号序列为)(()(，添加左右括号的位置如图所示。当添加左括号使得序列合规，再添加右括号使得序列匹配，这时的新序列就是满足题意的合法序列。故总方案数=添加左括号的方案数*添加右括号的方案数

#include 
#include 
using namespace std;
#define N 1000000007
long long func(string s){
    vector dd;
    vector > dp;
    int i,j;
    for(i=0;i<=1+s.size();i++){
        dd.push_back(0);
    }
    for(i=0;i<=1+s.size();i++){
        dp.push_back(dd);
    }
    dp[0][0]=1;
    for(i=1;i<=s.size();i++){//对每个括号进行判断
        if(s[i-1]=='('){
            for(j=1;j<=s.size();j++){
                dp[i][j]=dp[i-1][j-1];
            }
        }
        else{
            dp[i][0]=(dp[i-1][0]+dp[i-1][1])%N;
            for(j=1;j<=s.size();j++){
                dp[i][j]=(dp[i-1][j+1]+dp[i][j-1])%N;
            }
        }
    }
    for(i=s.size();i>=1;i--){//等同于下面的代码，求添加左括号的方案数
        if(s[i-1]==')'&&dp[i][0]!=0)
            return dp[i][0];
    }
    /*
    for(int i=0;i<=len;i++)//len是括号序列的长度，求添加左括号的方案数
        if(dp[len][i]!=0)
        	return dp[len][i];
        return -1;
    */
    return 1;
}
int main(int argc, char** argv) {
    string s;
    cin>>s;
    long long l=0;
    l=func(s);//求添加左括号的方案数
    int i;
    for(i=0;i

#include 
#include "bits/stdc++.h"
using namespace std;
vector s_array;
int judge(string & s){//判断新序列是否合法，且有没有和之前产生的合法新序列重复。若都没有，则return 1
    int i;
    stack zhan;
    for(i=0;i zhan;
    for(i=0;i>s;
    int sum=0;
    int i,j;
    ss= judges(s);//求出需要添加的左括号个数与右括号个数,并以字符串的形式返回
    dfs(s,sum,ss);//穷举
    cout<