【题目描述】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]”的情况当ki或kj-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(){ cins; //因为求最长合法子序列 所以初始化为0 memset(dp,0,sizeof(dp)); //枚举区间长度 len代表区间长度 //从小到大计算出所有所有区间的合法子序列长度 //计算大区间必须先计算出小的 for(int len2;lens.size();len){ //枚举左端点i (确保 ilen-1不越界) for(int i0;is.size()-len1;i){ int jilen-1;//右端点 //1尝试“包围结构”判断s[i]和s[j]是否配对 if((s[i](s[j]))||(s[i][s[j]])) //如果配对长度中间部分的长度 2 //这里的dp[i1][j-1]已经在len-2的时候算过了 dp[i][j]max(dp[i][j],dp[i1][j-1]2); //2尝试“拼接结构”枚举分割点k取最大值这个循环同时也覆盖了“丢弃 s[i]”或“丢弃 s[j]”的情况 for(int ki;kj;k){//分界线k dp[i][j]max(dp[i][j],dp[i][k]dp[k1][j]); } } } //输出字符串长度剪去最长合法子序列长度就是落单未配对的数量 //即为我们需要增加的数量 couts.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[i1][j-1])通用dp[i][j] min(dp[i][k] dp[k1][j])这也是一种解法但“最长合法子序列”的思路往往更容易理解因为它把问题变成了我们在LIS或LCS中熟悉的“求最长”模型。通过这道题我们可以看到区间 DP 的核心在于如何把大区间拆分成小区间。无论是“拼接”还是“包围”本质上都是在寻找问题的最优子结构。