线性动态规划：最长有效括号匹配子序列长度（允许间隔） 题目描述 给你一个只包含 '(' 和 ')' 的字符串 s，请你求出最长有效括号 子序列 的长度。 注意：这里的"子序列"不同于"子串"，它不要求连续，但要求保持字符的相对顺序。 同时，子序列需要是有效的括号序列，即： 每个 '(' 都有一个对应的 ')' 与之配对。 配对的 ')' 必须出现在对应的 '(' 之后。 配对的括号序列之间可以间隔其他字符，但整体必须满足有效性。 示例 1： 输入：s = "(()" 输出：2 解释：最长有效括号子序列可以是 "()"（取索引 0 和 1 的字符，或 1 和 2）。 示例 2： 输入：s = ")()())" 输出：4 解释：最长有效括号子序列是 "()()"（取索引 1,2,3,4 的字符）。 示例 3： 输入：s = "()(())" 输出：6 解释：整个字符串本身已经是有效括号序列，所以长度为 6。 解题过程 1. 问题理解 这个问题是求最长有效括号 子序列 的长度，而不是最长有效括号 子串 。 关键区别在于：子串必须连续，子序列可以跳过一些字符。 例如 s = "()(()"，最长有效括号子串是 "()" 长度为 2，但最长有效括号子序列是 "()()" 长度为 4（可以取索引 0,1,3,4 的字符）。 由于是子序列，我们需要考虑选择哪些 '(' 和 ')' 来形成配对，使得总有效长度最长。 2. 动态规划定义 我们定义一个二维数组 dp，其中： dp[ i][ j] 表示在子串 s[ i..j ]（包含 i 和 j）中，最长有效括号子序列的长度。 目标是求 dp[ 0][ n-1 ]，其中 n 是字符串长度。 当 i > j 时，子串为空，dp[ i][ j ] = 0。 当 i == j 时，单个字符不可能是有效括号对，dp[ i][ j ] = 0。 3. 状态转移思路 对于区间 [ i, j ]，考虑两种情况： (1) 字符 s[ j] 不参与构成有效括号对 此时最长有效括号子序列完全在子串 s[ i..j-1 ] 中，所以： dp[ i][ j] = dp[ i][ j-1 ] (2) 字符 s[ j] 参与构成有效括号对 因为 s[ j] 是 ')', 它需要与前面某个 '(' 配对。假设这个 '(' 的位置是 k（i ≤ k < j，且 s[ k ] == '('），那么我们将序列分成三部分： 在 k 之前的子串 s[ i..k-1 ] 中的有效括号对。 在 k 和 j 之间的子串 s[ k+1..j-1 ] 中的有效括号对。 加上 k 和 j 本身配对贡献的长度 2。 于是，dp[ i][ j] = max( dp[ i][ k-1] + dp[ k+1][ j-1] + 2 )，对所有满足 s[ k ]=='(' 的 k 取最大值。 注意：当 k = i 时，dp[ i][ k-1 ] 不存在，我们将其视为 0。 另外，如果 s[ j ] 是 '('，它不可能作为右括号参与配对，所以只有情况 (1) 适用。 4. 递推顺序 由于计算 dp[ i][ j] 时，会用到更短的区间（如 dp[ i][ j-1], dp[ i][ k-1], dp[ k+1][ j-1 ]），所以我们应该按照区间长度从小到大递推。 即：先计算所有长度为 1 的区间，再计算长度为 2 的区间，...，直到长度为 n 的区间。 5. 算法步骤 初始化 n = len(s)，dp[ n][ n ] 全部为 0。 外层循环长度 len 从 2 到 n（因为长度为 1 的区间 dp=0）。 内层循环起始点 i 从 0 到 n-len，计算 j = i+len-1。 先令 dp[ i][ j] = dp[ i][ j-1 ]（情况 1）。 如果 s[ j] == ')'，则尝试寻找 k 在 [ i, j-1] 范围内，且 s[ k ]=='('，那么： 候选值 = (dp[ i][ k-1] if k>i else 0) + (dp[ k+1][ j-1] if k+1 <= j-1 else 0) + 2 用候选值更新 dp[ i][ j ] 的最大值。 最终 dp[ 0][ n-1 ] 就是答案。 6. 复杂度分析 时间复杂度 O(n³)，因为最内层需要枚举 k。 空间复杂度 O(n²)。 7. 示例推演 以 s = "()(())" 为例，n=6。 初始化所有 dp[ i][ j ]=0。 长度 len=2： [ 0,1]: s[ 0]='(', s[ 1]=')'，k=0 匹配，dp[ 0][ 1 ] = 0 + 0 + 2 = 2。 [ 1,2]: s[ 1]=')', s[ 2]='('，s[ 2] 无法匹配，dp[ 1][ 2] = dp[ 1][ 1 ]=0。 [ 2,3]: s[ 2]='(', s[ 3]='('，dp[ 2][ 3 ]=0。 [ 3,4]: s[ 3]='(', s[ 4 ]=')'，配对得 2。 [ 4,5]: s[ 4]=')', s[ 5]=')'，dp[ 4][ 5 ]=0。 长度 len=3： [ 0,2]: 先 dp[ 0][ 2]=dp[ 0][ 1]=2；s[ 2 ]='(' 无法作为右括号，所以保持 2。 [ 1,3]: dp[ 1][ 3]=dp[ 1][ 2]=0；s[ 3 ]='(' 无法作为右括号。 [ 2,4]: dp[ 2][ 4]=dp[ 2][ 3]=0；s[ 4]=')'，找 k=2 或 3 为 '('，k=2 时：dp[ 2][ 4]=max(0, 0+dp[ 3][ 3 ]+2=2) → 更新为 2。 [ 3,5]: dp[ 3][ 5]=dp[ 3][ 4]=2；s[ 5]=')'，找 k=3 或 4 为 '('，k=3 时：候选=0+dp[ 4][ 4 ]+2=2，与现有 2 相同；k=4 不是 '('，所以保持 2。 继续直到长度 len=6： [ 0,5]: 先 dp[ 0][ 5]=dp[ 0][ 4]（需计算 dp[ 0][ 4 ] 等）。 最终 dp[ 0][ 5] 的计算中，会考虑 k=0 与 j=5 配对：dp[ 1][ 4 ] 是多少？ 计算 dp[ 1][ 4] 时，会考虑 k=2 与 j=4 配对等，最终得到 dp[ 0][ 5] = dp[ 1][ 4 ] + 2 = 4+2=6。 8. 优化思考 注意到在寻找 k 时，我们只需要考虑最后一个与 s[ j ]=')' 配对的 '(' 可能不是最优的，但通过枚举所有 k 可以保证正确性。 实际可以优化到 O(n²)，但 O(n³) 的解法对于 n 几百以内是可行的。 9. 边界情况 空字符串：返回 0。 全 '(' 或全 ')'：返回 0。 已经有效的括号序列：返回长度。