本篇鸡汤：没有人能替你遭受痛楚，也没有人能拿走你的刚强.
接待拜访：羑悻的小杀马特.-CSDN博客
本篇主题：带你解答洛谷的括号序列题目（绝对巧解）
制作日期：2025.01.10
附属专栏：C/C++题海汇总
目次
本篇简介：
一·标题先容：
二·思绪叙述：
2.1判定独立性：
2.2清闲法及添补gap表：
2.3添补dp表：
2.3.1dp状态方程规定:
2.3.2dp的状态转移方程推导及添补：
2.4·镜像法：
2.5细节处置惩罚：
三·代码汇总：
四.个人小结：
本篇简介：
本篇主体还是动态规划，之前篇先容了对它的解说概念，因此本篇就不做多表明，下面就是使用动态规划，团结概率论推导独立性公式，两步走，并采取镜像法优化一下，末了动态规划得到答案后，采取独立性求积方法得出答案。
一·标题先容：
洛谷链接： [蓝桥杯 2021 省 AB] 括号序列 - 洛谷
测试用例：
输入：((()
输出：5
二·思绪叙述：
当我们看到了括号添补类似题目，是不是想到了leetcode的有道括号天生题目，看着似乎：
链接：LCR 085. 括号天生 - 力扣（LeetCode）
下面我们展示下leetcode的代码：
- //思路：对于返回的字符串组合，可以考虑是否是决策树的叶子然后用决策树+dfs:即根据n也就是判断递归条件（剪枝）左右支为'('')'它们的选择，
- //然后画出决策树分析递归条件，完成dfs设计
- class Solution {
- public:
- //全局变量的设计：
- int left=0;
- int right=0;
- string path;
- vector<string> ret;
- vector<string> generateParenthesis(int n) {
- dfs(n);
- return ret;
- }
- void dfs(int &n){
- //递归出口：
- if(path.size()==2*n){
- ret.emplace_back(path);
- return;
- }
- //判断进入递归的条件（剪枝逆向）：
- if(left<n){
- path+='(';left++;
- dfs(n);
- path.pop_back();left--;//回溯
- }
- if(right<left){
- path+=')';right++;
- dfs(n);
- path.pop_back();right--;//回溯
- }
- }
- };
看到这里，根据我们上一篇的履历就很容易想到动态规划去解答，因此leetcode上面深度优先遍历的方法就寄掉了。
因此下面我们就用动态规划头脑去解答；但是它也是欠好想到；以致我们去看题解，是不是都看不懂好比：
这里可以看出要么就是三层for嵌套循环填dp，以及许多人会发现题解以致都看不懂，即便看懂还要琢磨很久才会明确（固然这里博主也是）；因此博主在这出一篇文章来表明一下，让各人可以更加明确这道题是怎样解答的。
那么下面我们就以标题给的例子来泛论：
2.1判定独立性：
起首，我们的任务就是要么添补右括号来干掉左括号，要么添补左括号来干掉右括号；反正就是要得到如许以最小的添加括号让它正当的添加方法数；那么下面我们说一下结论：
这里可以知道添加右括号使它正当（也就是使用右括号干掉左括号）的方法数和添加左括号方法数是独立的---->而标题要求是添加左括号和右括号是都行的,因此末了就可以转化成添加左括号方案数与右括号方案数之积（两者是独立的） 。
证明：
这里为什么可以得到上面说的结论，直接就把题目简朴化，单一化了：
这里须要用到的概率论的公式：
说白了就是A B两个变乱如果互不干扰，互不影响，那么此时两种同时发生的概率就是两者单独发生概率之积， 而本题呢？
我们给它的目标简化一下，使得它更贴近这，标题实在就是要求让我们要么增补左括号，要么增补右括号，对应把相反括号干掉，也就是所说的使得左右括号都正当；而我们增补右括号使得左括号正当并没有影响其他右括号的正当性（由于我们没有增补左括号）-->以是左右括号的正当性是独立的。
因此我们可以拆开来分别求它们单独的正当性种类然后求个积就是标题要的使得例子左右括号都正当的种类数。
这里留意下:标题所说最少添补括号的意思就是好比对于((()我们不能无缘无端让添加一对括号让它正当：((()()()()))类似如许。
因此我们可以得到一个公式：
ret=(re_left*re_right)%1e9+7 这里标题要求效果太大要取模
表明一下：也就是我们使左括号正当的种类*使右括号正当的种类。
那么也就是我们怎么求左括号和发的种类：这里我们引入一下清闲法（反面我们得知独立性后就基于判定左括号正当性来解说）。
2.2清闲法及添补gap表：
这里我们以左括号为例，就是我们每当多一个左括号就相称于多了一个可以添补右括号的清闲；但是当我们遍历到右括号，清闲个数可以明确成没变；但遍历到当前（0~当前清闲）能添补右括号个数要少一个（包管非负性，大于0才镌汰）
然后就是我们搞一个清闲数组纪录的就是前i个清闲中最多可以放多少个括号：gap（这里为了方便我们逐一对应，因此下标从1开始，对应的是前多少个清闲）
下面我们举个例子吧：
好比：((() :这里有三个清闲，具体变革gap数组的值（随着遍历）:1-->2-->3-->2（这留意是吧第三个清闲的最大容量减1）。
再好比：
由于多少个左括号就意味着可以增补多少右括号；但是清闲最大容量也就是增补括号的个数是随着与之反作用的括号干系的
因此下面重点：我们总结一下清闲规则（这里我们都以增补右括号使左括号正当来谈）：
①清闲的个数也就是左括号的个数；
②当碰到右括号的话清闲所容纳的括号数就镌汰（条件是大于0）。
下面就根据上述所讲添补清闲表gap：
l:纪录的左括号个数也就是清闲个数
- void init_gap() {//填充gap数组，也就是判断多少个空隙以及前多少个空隙的
- //最大容量
- for (int i = 0; i < N; i++) {
- if (s[i] == '(') {
- l++;
- gap[l] = gap[l - 1] + 1;
- }
- else gap[l] > 0 ? gap[l]-- : 1;//这里注意当干右括号的时候
- //因为是求得最少补充的左括号数，故不能出现负
- }
- }
我们gap数组存的都是遍历到当前清闲开始从0~i增补右括号最大个数；因此我们当添补dp表的时间遍历填写括号个数的要加一个判定：
添补括号个数<=gap[遍历到当前的清闲] 即 i<=gap[j]。
那又要问了为什么动态规划不是添补dp表为啥搞个清闲表；由于反面我们会添补dp就是根据多少个清闲（遍历到那边），最多可以添补多少个括号来添补的故肯定是有用的。
2.3添补dp表：
2.3.1dp状态方程规定:
那么起首我们肯定要先界说dp表的状态：
由于它是遍历到那边，然后又要在这段区间添补括号（多少个）使它变得正当，因此最好搞一个二维dp表。
那么我们团结上面搞的清闲表，规定状态：
- dp[i][j]代表遍历到第j个空隙处，可以在0~i个空隙内可以填充i个括号的种类数（这里我们遍历只按照左括号走）
这里由于让下标与现实意义对应及大概会出现状态方程本身初始化须要前边的值，我们选择多开，并手动初始化。
起首呢对于大多数人直接用头脑按照这个逻辑去想状态方程是啥样，肯定是困难的，因此我们搞一个简朴的例子带各人总结一下状态转移方程：
起首我们根据这个例子本身按照dp状态规定填好dp表；但是为什么第一行都填0呢 ？
这就是我们状态方程本身循环添补要用到的，须要我们提前举行初始化：
也就是把0个括号插入到0-l个清闲插入的方案:这里我们可以明确成把0个即插入“氛围”这种插法，故只有一种环境（固然有些委曲）；其次就是我们只能根据找规律，细致的话如果我们第一行不填写，可以发现如果都填写1的话可以得到一个公式：
实在就是我们谁人填写dp表的一个“1”形状dp值之和；我们可以根据这个公式来往上递推成“/”形状的dp值如许就无需再来一层for循环（就像上面说的o(N^3）一样复杂度的三层for了）只需取前面添补的两个dp值就好了。
如：
因此公式化简（也就是我们添补dp表要用的公式）：
固然了反面我们写的时间要对1e9+7取模（标题阐明，就不消说了吧，另有就是long long的奥妙之处了）
那dp填表的过程这个公式就ok吗？
固然还会有条件限定，这里我们在添补清闲表gap数组的时间就说了：
加上这个条件后添补dp就ok了。
这个条件就表明了为什么末了添补三个括号为0以及这么多位置填写0的缘故原由了。
末了我们要的是在0~j个清闲能添补的最大括号数的方案数（遍历到对应清闲，此清闲内里放的gap数组值）即：
如许我们就得到了上面所说的re_left值了（记取也是long long） 。
反面我们在去求re_right岂非也是写一个类似的两个函数去完成吗？
固然不消了，直接给他镜像一下，就等同于判定左括号的正当性了；这也就是本篇标题提到的镜像法的奥妙了。
2.4·镜像法：
这里固然名字起的多好高级，实在并不难明确，之以是这么利用就是为了让我们不消再多写函数就可以完成对右括号像左括号一样类似的查验；以是为什么起这个名字呢，下面看张图片：
如许就可以看出了我们要查抄右括号的正当性（增补左括号）；实在就是把它镜像一下然后再查验一次左括号的正当性就行了。
实在也不难利用：就是遍历一下原串，把左括号改成右括号，右括号改成左括号；然后再使用迭代器逆置一下就好
末了我们根据独立性返回两者之积就好了（但是留意范围long long ,其次就是取模）。
2.5细节处置惩罚：
也就是分享一下博主在写这道题碰到的困难，即一些细节题目没留意到而导致的：
好比：
①博主写的代码这里多数用的全局变量（长处就是可以让函数不消传参，弊端就是如果再次使用就要重新初始化）
- l=0;//再次填充gap是需要对它初始化0
- memset(dp,0,sizeof(dp));//再次用填充dp表也要对它初始化0
这就是re_left和re_right没有long long的效果；果真映射那句话：“不加long long 见祖宗” 。
③其次就是那些细节题目，好比添补gap表留意：
添补dp表要留意：
如许细节都处置惩罚好就大差不大了。
三·代码汇总：
- #include<bits/stdc++.h>using namespace std;using ll = long long;#define MAX 1000000007#define C 5000ll dp[C+1][C + 1] = { 0 };//体现把i个括号插入到前j个清闲的方案数int gap[C + 1] = { 0 };//下标是第几个清闲，值是清闲的最大左括号容量string s; int N; int l=0;//纪录左括号数目void init_gap() {//填充gap数组，也就是判断多少个空隙以及前多少个空隙的
- //最大容量
- for (int i = 0; i < N; i++) {
- if (s[i] == '(') {
- l++;
- gap[l] = gap[l - 1] + 1;
- }
- else gap[l] > 0 ? gap[l]-- : 1;//这里注意当干右括号的时候
- //因为是求得最少补充的左括号数，故不能出现负
- }
- }ll get_ans() { for (int i = 0; i <= l; i++) dp[0][i] = 1; for (int i = 1; i <= l; i++) { for (int j = 1; j <= l; j++) dp[i][j] = gap[j] >= i ? (dp[i - 1][j] + dp[i][j - 1]) % MAX:0; //添补的括号数目不能高出前多少个清闲所能容下的最大 } return dp[gap[l]][l];//输出的是把最大清闲数所能容的括号数填入的最多方式数}void mapping_r_to_l(){//增补左括号干掉右括号转化成增补右括号干掉左：//镜像一下子,使得写的干左括号的函数还可以用 reverse(s.begin(), s.end()); for (int i = 0; i < N; i++)s[i] =(s[i] == '(' ? ')' : '(');}int main() { cin >> s; N = s.size(); init_gap(); ll re_left = get_ans(); mapping_r_to_l(); l=0;//全局劣势 init_gap(); memset(dp,0,sizeof(dp));//全局劣势 ll re_right = get_ans(); cout << (re_left * re_right) % MAX << endl;//使用独立性 return 0;}
四.个人小结：
这里对于动态规划的题型做法就不总结了，由于上篇总结过啦，具体可看：【动态规划篇】步步带你深入解答乐成AC最优包罗题目（普通易懂版）-CSDN博客
别的就是对于不认识的标题，我们要对看看题解，看看大佬们是用什么奥妙的方法解答的，固然大概会看不懂，但是我们不要放弃，一天看不懂就多看几天，只要乐意学习别人的解法，总是会可以悟懂的（这里说一下博主写这篇文章实在也是学习了大佬的写法，固然也是看了好几天），以是我们本身不纯熟就要多多学习肯定的解法做好总结，尽最大大概去罗致它。这里博主发起如果看题解看不懂，只管找写的比力具体的博客去学习（博主自荐一下：可以参考向博主如许写的文章去看，去学习，如有不敷，指出来博主会努力修改）
还是那句话，只要乐意学肯定能学会的，关键还是在于你的决议。
对此，我之以是能写出这篇文章还要感谢一位博主写的它的文章，通过阅读，推测那位博主的文章；加上本身的明确才可创作出这篇文章（相称于对那位博主的文章的深刻表明以及加上了本身的明确吧）
鉴戒的博主文章链接：第十二届蓝桥杯B组省赛括号序列题解_蓝桥杯判定括号正当-CSDN博客
固然还是先发起把博主的文章读懂再去读这位博主的文章，究竟个人以为本身的文章对它表明了许多地方，更方便读者阅读。
感谢各人阅读！！！
|
发表于 2025-11-11 10:30:38