)
在区间动态规划的题库中，“括号匹配”类问题占据了半壁江山。
很多同学分不清“最长合法子串”和“最长合法子序列”的区别：
子串 (Substring)：必须连续。
子序列 (Subsequence)：可以不连续，中间可以跳过某些字符。
今天我们要解决的，就是一道经典的“子序列”问题。给定一个由(、)、[、]组成的字符串，求出其中最长的合法括号子序列的长度。
1. 问题背景
题目描述：
给定一个长度为n () 的字符串S。我们要在这个字符串中挑选出一些字符，保持它们在原串中的相对顺序不变，组成一个新的字符串。
要求这个新字符串必须是“合法的括号序列”。
合法定义的递归形式如下：
空串是合法的。
如果A是合法的，那么
(A)和[A]也是合法的。如果A和B是合法的，那么AB也是合法的。
目标：求这个最长合法子序列的长度。
样例：
输入：(( ))输出：4
输入：([)]输出：2 （可以是
()或者[]，但不能交叉）
2. 算法分析
这道题是典型的区间DP模型中的“端点匹配型”。
状态定义
我们定义dp[i][j]表示：字符串S中，从下标i到j的区间内，最长合法子序列的长度。
状态转移
对于区间[i, j]，我们依然采用“最后一步”的思维来推导。想要得到[i, j]的最优解，有两种大的构成方式：
策略一：两端匹配 (包围结构)
如果区间两端的字符S[i]和S[j]恰好能配对（即()或[]），那么它们有资格成为一对新的括号，包裹住中间的子序列。
dp[i][j] =
(注：前提是S[i]和S[j]必须匹配)
策略二：区间拼接 (并列结构)
无论两端是否匹配，最优解都有可能由两个独立的合法子序列拼凑而成。
我们枚举分割点k()，将大区间切分为[i, k]和[k+1, j]两部分：
dp[i][j] =
提示：这就解释了为什么代码中会有两层逻辑。第一层
if处理“包围”，第二层for k处理“拼接”。这两种策略覆盖了所有合法括号序列的生成规则。
3. 完整代码
//括号序列 #include <iostream> #include <cstring>//对应memset using namespace std; char s[510]; int dp[510][510];//dp[i][j]代表s[i]-s[j]之间最长的合法子序列长度 int main(){ int n; cin>>n; memset(dp,0,sizeof(dp));//初始化dp为0 //读入字符串，下标从1开始 scanf("%s",s+1); //枚举区间长度 len代表区间长度 从小到大计算出所有所有区间的合法子序列长度，计算大区间必须先计算出小的 for(int len=2;len<=n;len++){ for(int i=1;i<=n-len+1;i++){//枚举：左端点i (确保 i+len-1不越界) 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<<dp[1][n]; return 0; }4. 易错点与总结
子序列 vs 子串：
这道题求的是子序列，所以我们可以利用
dp[i][k] + dp[k+1][j]来进行拼接。如果是求子串（必须连续），则不能简单相加，需要更复杂的逻辑判断（通常涉及栈或更严格的 DP 状态）。为什么不需要专门处理“不选s[i]”的情况？
有同学会问，为什么方程里没有写
dp[i][j]=dp[i+1][j]？其实，代码中的
for(int k=i;k<j;k++)已经包含了这种情况。当k=i时，
dp[i][i] + dp[i+1][j]，因为dp[i][i]（单个字符）必然为0，所以这就等价于dp[i+1][j]。这个枚举k的循环很强大，它隐式地包含扔掉头和扔掉尾的决策。
循环顺序：
一定记得先枚举长度
len，因为计算大区间dp[i][j]时，必须保证其内部的小区间（如dp[i+1][j-1]）已经被计算过了。如果按i, j顺序枚举，可能会用到未更新的状态。
掌握了这道题，你就掌握了“括号区间 DP”的解题模板。以后遇到“括号匹配求最小添加数”之类的变种题，只需要把max改成min，逻辑是一样的。
