括号配对（信息学奥赛一本通- P1572）
【题目描述】
Hecy 又接了个新任务：BE 处理。BE 中有一类被称为 GBE。
以下是 GBE 的定义：
空表达式是 GBE
如果表达式 A 是 GBE，则 [A] 与 (A) 都是 GBE
如果 A 与 B 都是 GBE，那么 AB 是 GBE。
【输入】
输入仅一行，为字符串 BE。
【输出】
输出仅一个整数，表示增加的最少字符数
【输入样例】
[])【输出样例】
1【提示】
数据范围与提示：
对于 100% 的数据，输入的字符串长度小于 100。
在区间动态规划的题库中，括号匹配类问题占据了半壁江山。今天我们要解决的这道Hecy的GBE 任务，就是一个非常典型的代表。
题目要求我们通过最少的添加字符操作，把一个乱序的括号字符串变成合法的GBE序列。
1. 题目重述与分析
输入：一个由(,),[,]组成的字符串S。
输出：最少需要添加多少个字符，才能使S变成合法的括号序列？
数据范围：长度< 00。
核心思维转换
面对“最少添加”这类问题，直接思考在哪里加字符往往比较困难。我们可以尝试逆向思维：
如果我们能保留字符串中尽可能多的字符，让它们本身就构成一个合法的子序列。
那么，剩下的那些“无法匹配”的字符，就是必须通过添加字符来补全的。
结论：
最少添加数=字符串总长度-最长合法子序列的长度
这样，问题就从“求最少添加”转化为了“求区间内的最长合法子序列”。这正是区间DP最擅长的领域。
2. 动态规划设计
状态定义
定义dp[i][j]为：字符串中下标从i到j的子串中，最长合法子序列的长度。
状态转移方程
对于区间[i, j]，我们依然采用区间DP的标准“三板斧”：
1. 拼接结构
任何一个区间都可以从中间某个点k切开，其最长合法长度等于左边加右边。这也是区间 DP 的基础。
dp[i][j] =
注意：这个枚举其实也隐含了“放弃 s[i]”或者“放弃 s[j]”的情况（当k=i或k=j-1且边界值为0时）。
2. 包围结构
如果区间的左右端点s[i]和s[j]恰好能配对（即()或[]），那么它们可以把中间的最优解“包”起来，贡献 2 个长度。
=
边界与初始化
初始化：
memset(dp, 0)。长度为 1 的区间（如[）无法构成合法序列，长度自然为 0，符合逻辑。循环顺序：经典的枚举长度
len枚举左端点
i枚举分割点
k。
3. 完整代码
#include <iostream> #include <cstring>//对应memset #include <algorithm>//对应max using namespace std; string s; int dp[110][110];//dp[i][j]代表s[i]-s[j]的最长合法子序列 int main(){ cin>>s; //因为求最长合法子序列 所以初始化为0 memset(dp,0,sizeof(dp)); //枚举区间长度 len代表区间长度 //从小到大计算出所有所有区间的合法子序列长度 //计算大区间必须先计算出小的 for(int len=2;len<=s.size();len++){ //枚举：左端点i (确保 i+len-1不越界) for(int i=0;i<s.size()-len+1;i++){ int j=i+len-1;//右端点 //1尝试“包围结构”，判断s[i]和s[j]是否配对 if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')) //如果配对，长度=中间部分的长度 + 2 //这里的dp[i+1][j-1]已经在len-2的时候算过了 dp[i][j]=max(dp[i][j],dp[i+1][j-1]+2); //2尝试“拼接结构”，枚举分割点k，取最大值，这个循环同时也覆盖了“丢弃 s[i]”或“丢弃 s[j]”的情况 for(int k=i;k<j;k++){//分界线k dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]); } } } //输出字符串长度剪去最长合法子序列长度就是落单未配对的数量 //即为我们需要增加的数量 cout<<s.size()-dp[0][s.size()-1]; return 0; }4. 易错点与总结
下标问题：
string的下标是从0开始的，所以循环范围是0到n-1。转移顺序：一定要先处理
if配对的情况，再跑for k循环来更新最大值（或者像代码中这样，在for k中不断取max覆盖）。思维误区：有些同学会尝试直接定义
dp[i][j]为“最少添加数”。如果定义为最少添加数，转移方程变为：
若配对：
dp[i][j] = min(dp[i][j], dp[i+1][j-1])通用：
dp[i][j] = min(dp[i][k] + dp[k+1][j])
这也是一种解法，但“最长合法子序列”的思路往往更容易理解，因为它把问题变成了我们在LIS或LCS中熟悉的“求最长”模型。
通过这道题，我们可以看到：区间 DP 的核心在于如何把大区间拆分成小区间。无论是“拼接”还是“包围”，本质上都是在寻找问题的最优子结构。