括号配对（信息学奥赛一本通- 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。

核心思维转换

面对“最少添加”这类问题，直接思考在哪里加字符往往比较困难。我们可以尝试逆向思维：

1. 如果我们能保留字符串中尽可能多的字符，让它们本身就构成一个合法的子序列。

2. 那么，剩下的那些“无法匹配”的字符，就是必须通过添加字符来补全的。

3. 结论：

   最少添加数=字符串总长度-最长合法子序列的长度

这样，问题就从“求最少添加”转化为了“求区间内的最长合法子序列”。这正是区间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. 易错点与总结

1. 下标问题：string的下标是从0开始的，所以循环范围是0到n-1。

2. 转移顺序：一定要先处理if配对的情况，再跑for k循环来更新最大值（或者像代码中这样，在for k中不断取max覆盖）。

3. 思维误区：有些同学会尝试直接定义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 的核心在于如何把大区间拆分成小区间。无论是“拼接”还是“包围”，本质上都是在寻找问题的最优子结构。