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

题目描述

给定一个只包含 '(' 和 ')' 的字符串 s，你需要找出其中最长的有效括号子序列的长度。
注意：

• 有效括号子序列是指一个子序列（可以不连续！），其中的括号能够正确匹配。
• 例如，"()"、"()()"、"(())" 都是有效的，但 ")(" 无效。
• 子序列是原字符串中删除一些字符（也可以不删除）后，剩余字符的相对顺序保持不变得到的序列。

示例：
输入："())())"
输出：4
解释：最长有效括号子序列是 "(())" 或 "()()"，长度都是 4。

为什么是“动态规划”？

• 这个问题求的是最长有效括号子序列，有“最优子结构”特性：整个问题的最优解可以由子问题的最优解构造。
• 子序列不连续，但顺序必须保持，适合用区间或二维状态表示。

思路分析

1. 子序列匹配的特点
   对于有效括号匹配，关键是一对 '(' 和 ')' 能够匹配，但这两个字符在原字符串中可以不连续，只要顺序正确。
   例如："()(())" 的最长有效括号子序列可以是它本身（6 个字符全是有效的），但如果中间有未匹配的括号，可以跳过它们。

2. 状态定义
   定义 dp[i][j] 表示在子串 s[i...j] 中，最长有效括号子序列的长度。
   注意：i 和 j 是闭区间，且 i ≤ j。

3. 状态转移
   我们分两种情况考虑：

   • 情况1：字符 s[j] 不在最终的有效子序列中。
     那么 dp[i][j] = dp[i][j-1]。
   • 情况2：字符 s[j] 在最终的有效子序列中，并且它与前面的某个 '(' 匹配。
     假设与它匹配的 '(' 的位置是 k（i ≤ k < j 且 s[k] == '(' 且 s[j] == ')'），那么这对括号内部 (k+1...j-1) 必须也是一个有效子序列，并且括号外部 i...k-1 也要尽量长。
     因此：dp[i][j] = max(dp[i][j], dp[i][k-1] + 2 + dp[k+1][j-1])，其中 dp[i][k-1] 表示 k 左边的部分的最优解，dp[k+1][j-1] 表示这对括号内部的最优解。

   但这样直接枚举 k 会很慢。实际上，我们可以用另一种更简洁的递推方式。

更高效的动态规划

定义 dp[i][j] 同上。
考虑从小区间向大区间递推：

• 如果 s[i] 和 s[j] 可以匹配（即 s[i]=='(' 且 s[j]==')'），那么我们可以选择用它们作为一对匹配括号，内部用 dp[i+1][j-1] 的最优解，即：

  dp[i][j] = dp[i+1][j-1] + 2
  

• 否则，我们可以不将 s[i] 或 s[j] 作为匹配括号的端点，而是从中间某个位置 k 切开：

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

  这是因为子序列可以不连续，所以整个区间的最优解可以是两个不相交子区间的最优解之和。

注意：这里 dp[i][j] 的递推类似于“最长回文子序列”的区间 DP 思想，但匹配规则是括号匹配。

递推顺序

因为是区间 DP，我们按照区间长度从小到大计算：

1. 初始化：dp[i][i] = 0（单个字符无法匹配）。
2. 对每个区间长度 len 从 2 到 n，对每个起点 i，计算 j = i + len - 1，然后按上述公式计算。

示例推演

以 s = "())())" 为例，长度为 6。
我们只展示几个关键步骤：

• 初始化：所有长度为 1 的区间值为 0。
• 长度 2：
  • s[0:1]="()" 可匹配 → dp[0][1]=0+2=2。
  • s[1:2]="))" 不匹配 → 用分割：dp[1][2]=max(dp[1][1]+dp[2][2], ...)=0。
• 长度 3：
  • s[0:2]="())"：
    • 检查 s[0]='(' 与 s[2]=')' 匹配 → dp[0][2]=dp[1][1]+2=0+2=2。
    • 再与分割比较：dp[0][1]+dp[2][2]=2+0=2，取最大 2。
  • 其他区间类似。
• 最终 dp[0][5] 会计算出 4。

代码框架（Python风格）

def longestValidParenthesesSubseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n + 1):  # 区间长度
        for i in range(0, n - length + 1):
            j = i + length - 1
            # 情况1：不将 s[j] 作为匹配括号的右端
            dp[i][j] = dp[i][j-1]
            
            # 情况2：如果 s[j] 是 ')'，尝试与前面某个 '(' 匹配
            if s[j] == ')':
                for k in range(i, j):
                    if s[k] == '(':
                        # 匹配 (k, j)，内部是 [k+1, j-1]，左边是 [i, k-1]
                        left = dp[i][k-1] if k > i else 0
                        inner = dp[k+1][j-1] if k+1 <= j-1 else 0
                        dp[i][j] = max(dp[i][j], left + 2 + inner)
    
    return dp[0][n-1] if n > 0 else 0

优化

上述代码复杂度是 O(n³)，可以用预处理每个 ')' 对应的最可能匹配的 '(' 位置来优化，但为了清晰理解，这里给出基本动态规划思路。
实际上，这个问题还有一种贪心+栈的 O(n) 解法：

• 遍历字符串，用栈保存未匹配的 '('，遇到 ')' 时如果栈中有 '(' 就弹出并计数 +2，否则跳过。
• 但注意，子序列不连续，所以遇到栈空时的 ')' 可以跳过，因为它们不会在最终子序列中。
• 最终答案是匹配的对数 × 2。
  为什么贪心有效？因为括号匹配的顺序性，只要遇到可匹配的 ')' 就匹配，不会使结果更差。
  因此，这个问题的最优解是：有效匹配括号的对数 × 2，匹配方法就是从左到右扫描，用栈模拟匹配，统计匹配对数。
  复杂度 O(n)，空间 O(n) 或 O(1)（用计数器模拟栈）。

总结

• 区间动态规划是通用解法，适合理解“最长有效括号子序列”的结构。
• 贪心+栈是高效解法，利用了括号匹配的贪心性质。
• 重点在于区分“子串”和“子序列”的不同处理方式。