区间动态规划例题：最长有效括号子序列问题（最大长度）

题目描述
给定一个仅由字符 '(' 和 ')' 组成的字符串 s，找出其中最长的有效括号子序列的长度。有效括号子序列需满足：

1. 空序列或只包含 '(' 或 ')' 的序列不是有效括号序列；
2. 若子序列中每个左括号 '(' 都能在其右侧找到一个唯一的右括号 ')' 匹配，且整体匹配顺序合理，则该子序列有效。
   注意：子序列不要求连续，但需保持原字符串中的相对顺序。

例如：

• 输入 s = "()())"，最长有效括号子序列为 "()()"，长度为 4。
• 输入 s = ")(()())"，最长有效括号子序列为 "(()())"，长度为 6。

解题思路
使用区间动态规划，定义 dp[i][j] 表示子串 s[i:j+1] 中最长有效括号子序列的长度。需分情况讨论区间两端字符是否参与匹配。

步骤详解

1. 状态定义

   • dp[i][j]：字符串子区间 [i, j] 内最长有效括号子序列的长度。

2. 初始化

   • 单个字符无法形成有效括号序列，因此 dp[i][i] = 0。
   • 若区间长度为 2，仅当 s[i] == '(' 且 s[j] == ')' 时，dp[i][j] = 2；否则为 0。

3. 状态转移

   • 情况1：s[i] 和 s[j] 匹配（即 s[i] == '(' 且 s[j] == ')'）。
     此时最大长度可能为 dp[i+1][j-1] + 2，表示内部子区间的最长有效序列加上两端的匹配括号。
   • 情况2：枚举分割点 k（i ≤ k < j），将区间拆分为 [i, k] 和 [k+1, j]，取两部分之和的最大值：
     dp[i][j] = max(dp[i][k] + dp[k+1][j])。
   • 综合两种情况：

     dp[i][j] = max(dp[i+1][j-1] + 2, max_{k=i}^{j-1}(dp[i][k] + dp[k+1][j]))  
     条件：若 s[i] == '(' 且 s[j] == ')'  
     否则：dp[i][j] = max_{k=i}^{j-1}(dp[i][k] + dp[k+1][j])  
     

4. 计算顺序

   • 按区间长度从小到大遍历（长度 len 从 2 到 n），确保子区间结果已计算。

5. 示例演示
   以 s = "()())" 为例（索引 0~4）：

   • 初始化：所有长度为 1 的区间值为 0；长度为 2 时，dp[0][1] = 2（"()"），dp[1][2] = 0（")("），dp[2][3] = 2（"()"），dp[3][4] = 0（")"）。
   • 长度 3：
     • dp[0][2]：两端 s[0]='(' 和 s[2]='(' 不匹配，枚举分割点 k=1，得 dp[0][1] + dp[2][2] = 2 + 0 = 2。
     • 类似计算其他区间。
   • 最终 dp[0][4]：两端匹配（s[0]='('，s[4]=')'），比较 dp[1][3] + 2 与分割点最大值。其中 dp[1][3] = 2（子串 ")(" 无效，但分割后 dp[1][2] + dp[3][3] = 0 和 dp[1][1] + dp[2][3] = 0 + 2 = 2），因此 dp[0][4] = max(2+2, 分割点最大值) = 4。

6. 复杂度分析

   • 时间复杂度：O(n³)，需遍历所有区间及分割点。
   • 空间复杂度：O(n²)，用于存储 dp 表。

关键点

• 子序列不要求连续，但需保持顺序，因此区间两端字符可能不直接匹配，而是通过内部分割形成多个有效段。
• 初始化时注意长度为 2 的边界情况。