线性动态规划：最长有效括号匹配子序列长度 题目描述 给定一个只包含字符 '(' 和 ')' 的字符串 s ，要求找出最长的有效括号 子序列 的长度。有效括号子序列需满足： 是原字符串的一个子序列（可以通过删除某些字符得到，但不改变剩余字符的相对位置）； 是一个有效的括号序列（即每个左括号 '(' 都能找到一个对应的右括号 ')' 匹配，且整体匹配正确）。 例如： 输入 s = "()())" ，最长有效括号子序列是 "()()" ，长度为 4。 输入 s = ")(()())" ，最长有效括号子序列是 "(()())" ，长度为 6。 解题过程 步骤 1：理解子序列与子串的区别 子串要求连续，而子序列只需保持相对顺序，可以跳过某些字符。 本题中，我们不需要连续匹配，但需确保括号的匹配顺序正确。 步骤 2：定义状态 设 dp[i][j] 表示字符串 s 在区间 [i, j] 内的最长有效括号子序列的长度。目标是求 dp[0][n-1] （ n 为字符串长度）。 步骤 3：状态转移方程 考虑区间 [i, j] 如何由更小的区间转移而来： 基础情况 ：当 i > j 时，区间为空， dp[i][j] = 0 ；当 i == j 时，单个字符无法形成有效匹配（因为括号需成对）， dp[i][j] = 0 。 情况 1 ：如果 s[j] 不参与匹配，则直接继承子区间结果： dp[i][j] = dp[i][j-1] 。 情况 2 ：如果 s[j] 是右括号 ')' ，则尝试在区间 [i, j-1] 中找一个位置 k ，使得 s[k] 是左括号 '(' 且与 s[j] 匹配。匹配后，区间被分为三部分： [i, k-1] ：匹配前的部分； [k+1, j-1] ：匹配中间的部分； k 和 j 匹配成功，贡献长度 2。 转移方程为： dp[i][j] = max(dp[i][j], dp[i][k-1] + 2 + dp[k+1][j-1]) ，其中 k 需满足 s[k] == '(' 且 i ≤ k < j 。 步骤 4：递推顺序 由于大区间依赖更小的区间，我们需要按区间长度从小到大计算： 外层循环枚举区间长度 len ，从 2 到 n （因为有效匹配至少需要 2 个字符）； 内层循环枚举区间起点 i ，终点 j = i + len - 1 。 步骤 5：示例推导 以 s = "()())" 为例（索引从 0 开始）： 初始化：所有长度为 1 的区间值为 0。 长度 len = 2 ： [0,1] : s[0]='(', s[1]=')' ，匹配成功， dp[0][1] = 2 。 [1,2] : s[1]=')', s[2]='(' ，无法匹配， dp[1][2] = 0 。 其他区间类似。 长度 len = 3 ： [0,2] : 尝试匹配 s[2]='(' （失败），或继承 dp[0][1]=2 ，结果为 2。 继续计算至 len = 5 ，最终 dp[0][4] = 4 。 步骤 6：优化思路 上述方法时间复杂度为 O(n³)。可以优化为 O(n²)： 当 s[j] 是右括号时，直接寻找与它匹配的左括号位置 k ，而不需要遍历所有 k 。但需预处理每个右括号对应的匹配左括号位置（使用栈）。 最终答案 通过动态规划表逐层计算，最终 dp[0][n-1] 即为最长有效括号子序列的长度。