最长括号匹配子序列问题 题目描述： 给定一个只包含 '(' 和 ')' 的字符串 s，找出其中最长的有效括号子序列的长度。有效括号子序列需要满足： 空序列是有效的 如果序列 A 是有效的，那么 (A) 也是有效的 如果序列 A 和 B 都是有效的，那么 AB 也是有效的 解题过程： 问题分析 这是一个区间动态规划问题。我们需要在字符串 s 中找到一个子序列（不一定连续），使得这个子序列是有效的括号匹配序列，并且长度最长。 状态定义 定义 dp[ i][ j] 表示在子串 s[ i...j ] 中最长有效括号子序列的长度。 状态转移方程 考虑区间 [ i, j ] 的最长有效括号子序列，有以下几种情况： 情况1：如果 s[ i] 和 s[ j] 可以匹配（即 s[ i]=='(' 且 s[ j ]==')'） 那么 dp[ i][ j] = max(dp[ i+1][ j-1] + 2, dp[ i+1][ j], dp[ i][ j-1 ]) 情况2：如果 s[ i] 和 s[ j ] 不能匹配 那么 dp[ i][ j] = max(dp[ i+1][ j], dp[ i][ j-1 ]) 情况3：对于任意区间 [ i, j ]，我们还需要考虑分割点 k dp[ i][ j] = max(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j])，其中 i ≤ k < j 边界条件 当 i > j 时，dp[ i][ j ] = 0（空序列） 当 i = j 时，dp[ i][ j ] = 0（单个括号无法匹配） 计算顺序 由于区间动态规划的特性，我们需要按照区间长度从小到大进行计算： 先计算长度为 1 的区间 再计算长度为 2 的区间 依此类推，直到计算整个字符串 算法实现步骤 步骤1：初始化 n×n 的 dp 数组，所有元素设为 0 步骤2：处理长度为 2 的区间 步骤3：对于每个区间长度 len 从 2 到 n 步骤4：对于每个起始位置 i 从 0 到 n-len 步骤5：计算结束位置 j = i + len - 1 步骤6：如果 s[ i] 和 s[ j] 匹配，更新 dp[ i][ j ] 步骤7：考虑所有可能的分割点 k，更新 dp[ i][ j ] 步骤8：返回 dp[ 0][ n-1 ] 时间复杂度分析 需要遍历所有 O(n²) 个区间 每个区间需要检查 O(n) 个分割点 总时间复杂度为 O(n³) 空间复杂度为 O(n²) 优化思路 可以通过预处理来优化分割点的查找，但基本的三重循环方法已经能够解决这个问题。 这个算法通过系统地考虑所有可能的子区间和分割方式，确保找到最长的有效括号子序列。