区间动态规划例题：最长括号匹配子序列问题

题目描述
给定一个只包含字符 '(' 和 ')' 的字符串 s，要求找出其中最长的合法括号子序列的长度。合法括号序列定义为：

• 空字符串是合法括号序列；
• 如果 "A" 是合法括号序列，则 "(A)" 也是合法括号序列；
• 如果 "A" 和 "B" 是合法括号序列，则 "AB" 也是合法括号序列。

注意：子序列不要求连续，但必须保持原字符串中的相对顺序。例如，"()())" 的最长合法括号子序列是 "()()"，长度为 4。

解题思路
使用区间动态规划，定义 dp[i][j] 表示字符串 s 在区间 [i, j] 内的最长合法括号子序列的长度。通过枚举区间分割点，逐步合并子区间的解。

详细步骤

1. 状态定义

   • 设 dp[i][j] 表示子串 s[i:j+1] 的最长合法括号子序列长度。
   • 初始化：所有长度为 1 的区间 dp[i][i] = 0（单个字符无法构成合法括号）；若区间为空（i > j），则 dp[i][j] = 0。

2. 状态转移

   • 情况1：如果 s[i] 和 s[j] 可以匹配（即 s[i] == '(' 且 s[j] == ')'），则它们可以作为最外层括号包裹内部子序列：

     dp[i][j] = max(dp[i][j], dp[i+1][j-1] + 2)
     

   • 情况2：将区间 [i, j] 分割为两个子区间 [i, k] 和 [k+1, j]，合并两个子区间的解：

     dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j])
     

     其中 k 的取值范围为 i ≤ k < j。
   • 注意：两种情况需同时考虑，因为最优解可能由任意一种方式生成。

3. 遍历顺序

   • 按区间长度从小到大枚举（长度 len 从 2 到 n），确保计算 dp[i][j] 时所有更短的子区间已计算完成。

4. 示例分析
   以 s = "()())" 为例：

   • 初始化：所有单字符区间值为 0。
   • 长度 2："()" 匹配，dp[0][1] = 2；")(" 不匹配，值为 0。
   • 长度 3："()(" 可通过分割 [0,1] 和 [2,2] 得到 dp[0][2] = 2 + 0 = 2。
   • 长度 4："())" 中 s[0] 和 s[3] 不匹配，但分割后 dp[0][3] = dp[0][1] + dp[2][3] = 2 + 2 = 4。
   • 最终结果：dp[0][4] = 4，对应子序列 "()()"。

5. 复杂度分析

   • 时间复杂度：O(n³)（三重循环：区间长度、起点、分割点）。
   • 空间复杂度：O(n²)（存储二维 DP 表）。

关键点

• 合法括号子序列不要求连续，因此需枚举所有可能的分割点。
• 当首尾字符匹配时，直接包裹内部子序列是一种潜在最优解。
• 区间 DP 的经典遍历顺序确保子问题优先求解。