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

题目描述
给定一个只包含字符 '(' 和 ')' 的字符串 s，要求找出其中最长的合法括号匹配子序列的长度。注意：子序列不要求连续，但必须保持原字符串中的相对顺序，且每个左括号必须有对应的右括号匹配。例如，字符串 "()())" 的最长合法括号子序列长度为 4（对应 "()()" 或 "(())"）。

解题思路

1. 问题分析

   • 与最长有效括号子串问题（要求连续）不同，本题允许非连续的子序列，因此更适合用区间动态规划求解。
   • 关键观察：若一个括号序列是有效的，其任意子区间的最优解可以通过组合更小区间的最优解得到。

2. 定义状态

   • 设 dp[i][j] 表示字符串 s 在区间 [i, j] 内的最长合法括号子序列的长度。

3. 状态转移

   • 情况1：不包含端点 i 或 j 时，直接继承子区间结果：

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

   • 情况2：若 s[i] 和 s[j] 匹配（即 s[i]=='(' 且 s[j]==')'），则可能将两端点加入最优解：

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

   • 情况3：将区间 [i, j] 分割为两部分 [i, k] 和 [k+1, j]，合并结果：

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

4. 初始化与遍历顺序

   • 初始化：单个字符无法匹配，dp[i][i] = 0；空区间 dp[i][j] = 0（当 i > j）。
   • 遍历顺序：按区间长度 len 从小到大（len 从 2 到 n），确保子区间已计算。

5. 最终答案

   • 结果为 dp[0][n-1]，即整个字符串的最长合法括号子序列长度。

示例推导
以 s = "()())" 为例（下标从0开始）：

• 初始化：所有长度为1的区间值为0。
• 长度2：
  • [0,1]: "()" 匹配，dp[0][1]=2。
  • [1,2]: ")(" 不匹配，继承子区间得 max(dp[1][1], dp[2][2])=0。
  • 类似计算其他长度2区间。
• 长度3：
  • 例如 [0,2]="()("：
    • 两端不匹配，继承 max(dp[1][2], dp[0][1])=max(0,2)=2。
    • 分割：dp[0][0]+dp[1][2]=0，dp[0][1]+dp[2][2]=2，最终取 2。
• 最终 dp[0][4] 通过组合 dp[0][1]+dp[2][4] 或两端匹配等方式得到 4。

关键点总结

• 区间DP通过枚举区间分割点，灵活处理非连续子序列的匹配问题。
• 注意区分子序列与子串的差异：子序列允许跳过部分字符，因此需考虑区间分割的情况。
• 时间复杂度 O(n³)，可用优化（如记录匹配点）降至 O(n²)，但本题标准解法以清晰性为主。