区间动态规划例题：最长有效括号子序列问题 题目描述 给定一个仅包含字符 '(' 和 ')' 的字符串 s ，找出其中最长的有效括号子序列的长度。有效括号子序列需满足： 子序列不要求连续，但需保持原字符串中的相对顺序； 子序列是有效的，即每个左括号 '(' 都能与一个右括号 ')' 正确匹配。 例如： 输入 s = "()())" ，最长有效括号子序列为 "()()" ，长度为 4。 输入 s = ")(()())" ，最长有效括号子序列为 "(()())" ，长度为 6。 解题思路 此问题需通过区间动态规划求解。定义 dp[i][j] 表示子串 s[i:j+1] 中最长有效括号子序列的长度。需分情况讨论子串两端字符是否匹配，并结合内部子区间的结果。 步骤详解 初始化 创建二维数组 dp ，大小为 n × n （ n 为字符串长度），初始化为 0。 单个字符无法形成有效括号，因此所有 dp[i][i] = 0 。 区间长度遍历 按区间长度 len 从 2 到 n 遍历（因为长度 1 的区间无效）。 对于每个区间起点 i ，计算终点 j = i + len - 1 ，且需满足 j < n 。 状态转移 情况1 ：若 s[j] 是右括号 ')' ，则可能与其左侧的某个左括号匹配。遍历中间点 k （从 i 到 j-1 ），检查 s[k] 是否为 '(' ： 若匹配成功，则 dp[i][j] 可能等于 dp[i][k-1] + 2 + dp[k+1][j-1] （即 k 与 j 匹配，加上中间两部分子区间的结果）。 情况2 ：无论两端是否匹配，还需考虑不匹配的情况，即直接继承子区间的最优解： dp[i][j] = max(dp[i][j], dp[i][j-1], dp[i+1][j]) 。 注意边界处理：当 k 为区间起点时， dp[i][k-1] 视为 0。 示例演示 以 s = "()())" 为例： 区间 [0,4] ： 检查 j=4 为 ')' ，遍历 k 发现 k=3 的 s[3]='(' 与之匹配。 匹配后结果为 dp[0][2] + 2 + dp[4][3] （空区间为 0），即 dp[0][2]=2 （子串 "()" ）加 2 得 4。 最终 dp[0][4] = 4 。 复杂度分析 时间复杂度：O(n³)，需遍历所有区间及中间点。 空间复杂度：O(n²)，用于存储 dp 表。 关键点 重点处理右括号与左侧左括号的匹配可能性，避免遗漏非连续匹配。 状态转移时需综合匹配和不匹配两种情况，确保最优解被覆盖。