线性动态规划：最长有效括号匹配子序列长度（允许间隔） 题目描述 给定一个只包含 '(' 和 ')' 的字符串 s ，找出最长的有效括号匹配子序列的长度。注意：子序列不要求连续，但必须保持原字符串中的相对顺序，并且每个左括号 '(' 必须有一个对应的右括号 ')' 匹配。例如，字符串 "()())" 的最长有效括号子序列是 "()()" ，长度为 4。 解题过程 问题分析 有效括号序列需满足：左右括号数量相等，且任意前缀中左括号数不少于右括号数。 子序列不要求连续，因此需动态规划记录区间内的匹配状态。 定义状态 设 dp[i][j] 表示字符串 s 在区间 [i, j] 内的最长有效括号子序列长度。 目标：求 dp[0][n-1] （ n 为字符串长度）。 状态转移 基础情况 ：当 i > j 时，区间为空， dp[i][j] = 0 。 情况1 ：不考虑 s[i] ，则 dp[i][j] = dp[i+1][j] 。 情况2 ：若 s[i] 是右括号，它无法作为匹配起点，直接跳过（同情况1）。 情况3 ：若 s[i] 是左括号，尝试在区间 [i+1, j] 中寻找一个右括号 s[k] 与之匹配。匹配后，区间被分为三部分： [i+1, k-1] ：内部子序列，长度 dp[i+1][k-1] 。 [k+1, j] ：剩余部分，长度 dp[k+1][j] 。 加上匹配的 s[i] 和 s[k] ，总长度为 dp[i+1][k-1] + 2 + dp[k+1][j] 。 遍历所有可能的 k （ i < k ≤ j 且 s[k] 为 ')' ），取最大值。 综合以上情况， dp[i][j] 取所有可能的最大值。 递推顺序 需按区间长度从小到大计算，因为长区间依赖短区间的结果。 外层循环：区间长度 len 从 2 到 n （因为匹配至少需要两个字符）。 内层循环：区间起点 i ，终点 j = i + len - 1 。 举例说明 以 s = "()())" 为例： 初始化：所有长度为1的区间 dp[i][i] = 0 （单括号无法匹配）。 长度2： dp[0][1] 对应 "()" ，匹配成功，长度为2。 长度3： dp[0][2] 对应 "()(" ，最大值为 dp[1][2] （内部无匹配）或匹配 s[0] 和 s[1] （已计算），结果为2。 最终 dp[0][4] 通过匹配 s[0] 与 s[1] 、 s[3] 与 s[4] 得到长度4。 算法优化 时间复杂度 O(n³)，可通过预处理右括号位置优化至 O(n²)，但核心思路不变。 总结 本题通过区间动态规划模型，以左右指针划分区间，枚举匹配点，逐步合并子问题解，得到最长有效括号子序列长度。