最长括号匹配子序列问题 题目描述： 给定一个只包含 '(' 和 ')' 的字符串 s，找出最长的有效括号子序列的长度。有效括号子序列定义为：该子序列中每个左括号 '(' 都有一个对应的右括号 ')' 正确匹配，并且匹配关系是合法的。 解题过程： 问题分析： 我们需要找到一个子序列（不一定连续），使其形成有效的括号匹配 与最长有效括号子串不同，子序列不要求字符连续 例如：s = "()())" 的最长有效括号子序列长度为4（"()()"） 动态规划定义： 定义 dp[ i][ j] 表示字符串 s 在区间 [ i, j ] 内的最长有效括号子序列长度。 状态转移方程： 基本情况：当 i > j 时，dp[ i][ j ] = 0（空区间） 当 i = j 时，dp[ i][ j ] = 0（单个字符无法形成匹配） 对于区间 [ i, j ]： a) 如果 s[ j] 不参与匹配：dp[ i][ j] = dp[ i][ j-1 ] b) 如果 s[ j ] 参与匹配，需要找到与之匹配的左括号： 遍历 k 从 i 到 j-1： 如果 s[ k] == '(' 且 s[ j ] == ')'，那么： dp[ i][ j] = max(dp[ i][ j], dp[ i][ k-1] + dp[ k+1][ j-1 ] + 2) 计算顺序： 由于需要小区间的结果来计算大区间，我们按区间长度从小到大计算： 先计算长度为1的区间 然后计算长度为2的区间 依次递增，直到整个字符串 具体步骤示例： 以 s = "()())" 为例： 初始化： 所有长度为1的区间：dp[ i][ i ] = 0 长度为2的区间： dp[ 0][ 1]：s[ 0]='(', s[ 1 ]=')' → 匹配，长度为2 dp[ 1][ 2]：s[ 1]=')', s[ 2 ]='(' → 不匹配，长度为0 dp[ 2][ 3]：s[ 2]='(', s[ 3 ]=')' → 匹配，长度为2 dp[ 3][ 4]：s[ 3]=')', s[ 4 ]=')' → 不匹配，长度为0 长度为3的区间： dp[ 0][ 2]：考虑s[ 2 ]是否匹配 与s[ 0]匹配：dp[ 1][ 1 ] + 2 = 0 + 2 = 2 与s[ 1 ]不匹配 最终：max(dp[ 0][ 1 ], 2) = 2 长度为4的区间： dp[ 1][ 4]：考虑s[ 4 ]是否匹配 与s[ 1]匹配：dp[ 2][ 3 ] + 2 = 2 + 2 = 4 最终结果为4 算法实现要点： 时间复杂度：O(n³)（可通过优化到O(n²)） 空间复杂度：O(n²) 最终结果：dp[ 0][ n-1 ] 即为整个字符串的最长有效括号子序列长度 优化思路： 可以记录每个位置可能的最优匹配，将时间复杂度优化到O(n²)，但基本思路保持不变。