线性动态规划：最长有效括号匹配子串（栈与动态规划结合解法） 题目描述 给定一个仅包含字符 '(' 和 ')' 的字符串 s ，要求找出最长的有效（格式正确）括号子串的长度。例如，字符串 "(()" 的最长有效括号子串长度为 2 （对应 "()" ）；字符串 ")()())" 的最长有效括号子串长度为 4 （对应 "()()" ）。 解题过程 1. 问题分析 有效括号子串需满足： 每个左括号 '(' 必须有对应的右括号 ')' 匹配； 匹配的括号对必须连续正确嵌套或并列（如 "()()" 或 "(())" ）。 直接暴力枚举所有子串会超时，需用动态规划或栈优化。 2. 动态规划定义状态 定义 dp[i] 表示以字符 s[i] 结尾的最长有效括号子串的长度。注意：有效子串必须以 ')' 结尾，因此遇到 '(' 时 dp[i] = 0 。 3. 状态转移推导 分情况讨论： 情况1 ：当 s[i] = ')' 且 s[i-1] = '(' 时，形如 "...()" 。 此时 dp[i] = dp[i-2] + 2 （如果 i-2 存在，否则为 2 ）。 例如 s = "()" ， i=1 ： dp[1] = dp[-1]（取0） + 2 = 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] 其中 dp[i-1] 是前面已匹配的长度， +2 为新增匹配对，最后一项是匹配括号对之前的有效长度。 例如 s = "(())" ， i=3 ： dp[2]=0 （因 s[2]=')' 且 s[1]=')' ，但 s[0]='(' 匹配 s[3] ）， dp[3] = dp[2] + 2 + dp[-1] = 0+2+0=2 ？错误！正确计算： 实际 i=3 时， dp[2]=2 （因为 s[0..2]="(())" 未结束），需重新推算： 更清晰例子： s = "()(())" ， i=5 ： dp[4]=2 （对应 "(())" 中的内部 "()" ）， i=5 时， s[5 - dp[4] - 1] = s[2] = '(' ，匹配成功， dp[5] = dp[4] + 2 + dp[1] = 2+2+2=6 。 4. 算法步骤 初始化 dp 数组为0，长度同 s 。 遍历 i 从 1 到 n-1 （因为 i=0 时无法形成有效子串）： 若 s[i]=')' 且 s[i-1]='(' ： dp[i] = (dp[i-2] if i>=2 else 0) + 2 若 s[i]=')' 且 s[i-1]=')' ： 设 j = i - dp[i-1] - 1 ， 若 j>=0 且 s[j]='(' ： dp[i] = dp[i-1] + 2 + (dp[j-1] if j>=1 else 0) 最终结果为 max(dp) 。 5. 示例演示 以 s = "()(())" 为例： i=1 ： s[1]=')' , s[0]='(' → dp[1]=0+2=2 i=2 ： '(' → dp[2]=0 i=3 ： '(' → dp[3]=0 i=4 ： s[4]=')' , s[3]='(' → dp[4]=dp[2]+2=0+2=2 i=5 ： s[5]=')' , s[4]=')' ， j=5-2-1=2 ， s[2]='(' → dp[5]=2+2+dp[1]=4+2=6 最终最大长度 max(dp)=6 ，对应整个字符串。 6. 复杂度分析 时间复杂度：O(n)，遍历一次字符串。 空间复杂度：O(n)，用于存储 dp 数组。