线性动态规划：最长有效括号匹配子序列长度

题目描述
给定一个仅由 '(' 和 ')' 组成的字符串 s，要求找出最长的有效括号匹配子序列的长度。注意，子序列不要求连续，但必须满足括号匹配的规则（即每个左括号都有对应的右括号匹配，且匹配顺序正确）。例如，字符串 "()())" 的最长有效括号子序列长度为 4（对应子序列 "()()" 或 "(())"）。

解题思路
此问题可以通过动态规划解决。定义 dp[i][j] 表示字符串 s 在子区间 [i, j] 内的最长有效括号匹配子序列的长度。我们需要填充一个二维 DP 表，最终答案是 dp[0][n-1]，其中 n 是字符串长度。

步骤详解

1. 初始化

   • 创建一个大小为 n x n 的二维 DP 表，初始值全为 0。
   • 对于任意 i > j 的区间，长度为 0，直接忽略。
   • 对于长度为 1 的区间（即 i = j），单个括号无法匹配，因此 dp[i][i] = 0。

2. 状态转移
   考虑区间 [i, j]，分两种情况：

   • 情况1：如果 s[i] 和 s[j] 可以匹配（即 s[i] == '(' 且 s[j] == ')'），则最优解可能包含这对匹配的括号，即：

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

   • 情况2：无论 s[i] 和 s[j] 是否匹配，我们都可以将区间分割为两部分，取最大值：

     dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j])，其中 k 从 i 到 j-1
     

     这一步是为了处理嵌套或并列的匹配情况，例如 "()()" 或 "(())"。

3. 填充顺序
   由于长区间依赖于短区间的结果，我们需要按区间长度从小到大填充 DP 表。具体顺序为：

   • 第一层循环：长度 len 从 2 到 n（因为长度为 1 的区间已初始化为 0）。
   • 第二层循环：起始索引 i 从 0 到 n - len。
   • 计算结束索引 j = i + len - 1。

4. 示例推导
   以 s = "()())" 为例（n=5）：

   • 长度 len=2：
     • [0,1]: "()" 匹配，dp[0][1] = 2。
     • [1,2]: ")(" 不匹配，dp[1][2] = 0。
     • 其他区间类似。
   • 长度 len=3：
     • [0,2]: "()("，末尾不匹配，但可分割为 [0,1] 和 [2,2]：dp[0][2] = 2 + 0 = 2。
   • 最终 dp[0][4] 通过组合 dp[0][1] 和 dp[2][4] 得到 4。

复杂度分析

• 时间复杂度：O(n³)，因需要三重循环（区间长度、起始点、分割点）。
• 空间复杂度：O(n²)，用于存储 DP 表。

优化提示
实际可通过观察减少不必要的分割计算，但基础解法需牢固掌握区间 DP 的思想。此方法也适用于其他括号匹配变种问题（如统计数量、带通配符等）。