区间动态规划例题：最长有效括号子串问题（不同解法版本） 题目描述： 给定一个只包含 '(' 和 ')' 的字符串 s，找出最长有效（格式正确且连续）括号子串的长度。 示例： 输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()" 输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()" 解题过程： 问题分析 有效括号子串需要满足： 每个左括号 '(' 必须有对应的右括号 ')' 匹配 匹配的括号对必须正确嵌套 我们需要找到最长的连续有效子串 DP状态定义 定义 dp[ i ] 表示以第 i 个字符结尾的最长有效括号子串的长度。 状态转移方程 情况1：当 s[ i] = ')' 且 s[ i-1 ] = '(' 时 dp[ i] = dp[ i-2 ] + 2 （如果 i >= 2） dp[ i] = 2 （如果 i < 2） 情况2：当 s[ i] = ')' 且 s[ i-1 ] = ')' 时 如果 s[ i - dp[ i-1] - 1 ] = '('，那么： dp[ i] = dp[ i-1] + 2 + dp[ i - dp[ i-1] - 2 ] 详细解释 对于情况1：形如 "....()" 直接在前一个有效长度基础上加2 对于情况2：形如 "....))" 检查前一个 ')' 对应的有效括号子串之前是否是 '(' 如果是，则形成新的有效对，并连接前面的有效子串 算法步骤 初始化 dp 数组为0 遍历字符串，i从1到n-1 根据字符情况应用状态转移方程 记录最大的 dp[ i ] 作为答案 示例演示 以 s = ")()())" 为例： i=0: s[ 0]=')'，dp[ 0 ]=0 i=1: s[ 1]='('，dp[ 1 ]=0（左括号不能作为有效结尾） i=2: s[ 2]=')'，且 s[ 1 ]='('，属于情况1 dp[ 2] = dp[ 0 ] + 2 = 0 + 2 = 2 i=3: s[ 3]='('，dp[ 3 ]=0 i=4: s[ 4]=')'，且 s[ 3 ]='('，属于情况1 dp[ 4] = dp[ 2 ] + 2 = 2 + 2 = 4 i=5: s[ 5]=')'，且 s[ 4 ]=')'，属于情况2 检查 i-dp[ 4]-1 = 5-4-1 = 0，s[ 0 ]=')'，不匹配 dp[ 5 ]=0 最长有效长度为4。 复杂度分析 时间复杂度：O(n)，只需遍历一次字符串 空间复杂度：O(n)，用于存储dp数组 这种方法通过动态规划巧妙地处理了括号匹配的连续性要求，确保找到最长的有效子串。