线性动态规划：最长有效括号子序列（Longest Valid Parentheses Subsequence）

题目描述

给定一个只包含 '(' 和 ')' 的字符串 s，请找出该字符串的最长有效括号子序列的长度。注意，这里要求的是子序列，而不是连续的子串。有效括号子序列的定义是：可以通过删除原字符串中的某些字符（也可以不删除）得到一个有效的括号序列。

有效括号序列满足：

• 空字符串是有效的。
• 如果 A 是有效的，那么 (A) 也是有效的。
• 如果 A 和 B 是有效的，那么 AB 也是有效的。

例如：

• 输入：s = "()())()"，输出：6（最长有效括号子序列可以是 "()()()" 或 "(())()"，长度均为6）。
• 输入：s = ")("，输出：0（无法构成任何有效括号子序列）。

解题思路

这个问题是最长有效括号子串的变种，但区别在于子序列不要求连续。我们可以用动态规划来解决。

状态定义：
定义 dp[i][j] 表示在子串 s[i:j+1]（闭区间）中，匹配的最长有效括号子序列长度。注意，这里的“匹配”指的是子序列中所有括号都能正确配对。

状态转移方程：
我们考虑区间 [i, j]。

1. 情况1：如果 s[j] 是左括号 '('，它无法作为右括号来匹配，所以 dp[i][j] = dp[i][j-1]（即不考虑s[j]）。

2. 情况2：如果 s[j] 是右括号 ')'，我们尝试在 [i, j-1] 中找到一个左括号 '(' 与之匹配。假设这个左括号位置是 k（i ≤ k ≤ j-1），那么我们可以将区间分成三部分：

   • 左括号 s[k] 和右括号 s[j] 匹配，贡献长度为 2。
   • 区间 [i, k-1] 中的最长有效括号子序列长度：dp[i][k-1]（如果 k-1 < i，则长度为0）。
   • 区间 [k+1, j-1] 中的最长有效括号子序列长度：dp[k+1][j-1]。
     因此，以 k 为匹配左括号时，总长度为：
     dp[i][k-1] + 2 + dp[k+1][j-1]。
     我们需要遍历所有可能的 k（s[k] = '('），取最大值。

   同时，我们还要考虑不匹配 s[j] 的情况，即 dp[i][j-1]。
   所以最终转移为：

   dp[i][j] = max(dp[i][j-1], max_{k=i..j-1, s[k]='('} (dp[i][k-1] + 2 + dp[k+1][j-1]))
   

   其中，如果 k-1 < i，则 dp[i][k-1] 视为 0；如果 k+1 > j-1，则 dp[k+1][j-1] 视为 0。

边界条件：

• 当区间长度为1（i = j）时，有效括号子序列长度不可能为1（因为单个括号无法匹配），所以 dp[i][i] = 0。
• 当区间为空（i > j）时，长度为 0。

最终答案：
整个字符串 s 的最长有效括号子序列长度就是 dp[0][n-1]，其中 n 是字符串长度。

逐步计算示例

以 s = "()())()" 为例，长度 n=7。
我们按区间长度从小到大计算 dp[i][j]：

1. 区间长度 L=1（i=j）：所有 dp[i][i] = 0。
2. 区间长度 L=2：
   • [0,1]：s="()"，s[1]=')'，找到 k=0（s[0]='('），则 dp[0][1] = max(dp[0][0], dp[0][-1]+2+dp[1][0])。注意 dp[0][-1] 和 dp[1][0] 视为0，所以结果为 2。
   • 类似计算其他长度为2的区间，只有当 s[i]='(' 且 s[j]=')' 时结果为2，否则为0。
3. 区间长度 L=3 及更大：
   以 [0,3] 为例，s="()()"，j=3 是 ')'，遍历 k=0..2 中 s[k]='(' 的位置：
   • k=0：dp[0][-1]+2+dp[1][2] = 0+2+dp[1][2]。dp[1][2] 对应 s[1..2]="()"，长度为2，所以总长度 4。
   • k=2：dp[0][1]+2+dp[3][2]，dp[0][1]=2，dp[3][2] 区间无效为0，总长度 4。
     因此 dp[0][3]=4。
4. 继续计算所有区间，最终 dp[0][6] = 6。

优化

上述方法时间复杂度为 O(n³)，因为需要遍历区间和匹配位置 k。我们可以进一步优化：

• 对于每个右括号 s[j]，我们可以尝试匹配最近的左括号。但由于是子序列，匹配的左括号可能不是最近的。但可以证明，对于区间 [i, j]，如果 s[j]=')'，我们只需考虑两种选择：
  1. 不匹配 s[j]：dp[i][j-1]。
  2. 匹配 s[j]：在 [i, j-1] 中找到一个 '(' 匹配，但更优的策略是匹配最后一个可用的 '('？这不一定，因为子序列可以不连续。实际上，我们可以用另一种动态规划状态：
     定义 dp[i][j] 表示区间 [i, j] 中的最长有效括号子序列长度，并且该子序列以 s[j] 结尾（如果 s[j] 被使用的话）。但这种状态转移也较复杂。

另一种常见思路是转化为最长公共子序列（LCS）问题：
将原字符串 s 与它的一个“翻转并取反”字符串（即 '(' 变成 ')'，')' 变成 '('）做 LCS，但需要保证括号匹配顺序。更直接的方法是：

• 设 balance 表示当前未匹配的左括号数量。
• 从前往后扫描，维护两个值：当前有效子序列长度和当前未匹配的左括号数。但实际上，我们可以用 贪心 结合动态规划来做到 O(n²)：
  定义 f[i][c] 表示考虑前 i 个字符，当前未匹配的左括号数为 c 时的最长有效子序列长度。状态转移时，对每个字符选择是否放入子序列。

不过，标准的区间动态规划已经足够清晰。在实际实现时，我们可以用记忆化搜索来简化代码逻辑。

最终解法（优化版）

我们可以用一维动态规划：
定义 dp[i] 表示以 s[i] 结尾的最长有效括号子序列长度，但需要记录未匹配的左括号位置。但由于子序列不连续，这种方法并不直接。

更实用的解法是基于栈和贪心的动态规划：

1. 从左到右扫描字符串，维护一个栈，栈中存放未匹配的字符索引（主要是 '('）。
2. 同时，用数组 best 记录每个位置作为结尾的最长有效括号子序列长度。
3. 当遇到 ')' 时，尝试从栈中弹出一个 '(' 进行匹配。如果匹配成功，则当前有效长度 = 2 + 匹配的左括号前一个位置的最长有效长度。
4. 但因为是子序列，我们可能跳过一些字符，所以需要记录所有可能的状态转移。

但最简单的实现仍是区间动态规划，这里给出 O(n³) 的伪代码：

n = len(s)
dp = [[0]*n for _ in range(n)]
for L in range(2, n+1):          # 区间长度
    for i in range(n-L+1):
        j = i+L-1
        # 不取 s[j]
        dp[i][j] = dp[i][j-1]
        if s[j] == ')':
            for k in range(i, j):
                if s[k] == '(':
                    left = dp[i][k-1] if k>i else 0
                    mid = dp[k+1][j-1] if k+1 <= j-1 else 0
                    dp[i][j] = max(dp[i][j], left + 2 + mid)
return dp[0][n-1]

总结

最长有效括号子序列问题通过区间动态规划可以清晰解决，但需要注意状态转移时考虑匹配的多种可能。虽然时间复杂度较高（O(n³)），但对于中等长度字符串仍然可行。此外，我们可以进一步优化到 O(n²)，思路是固定右括号，只考虑最优匹配的左括号，但这需要更复杂的状态设计。本题的核心在于理解子序列匹配与连续子串匹配的区别，并灵活运用区间分解的思想。