最长有效括号子串 题目描述 给定一个只包含 '(' 和 ')' 的字符串 s，找出最长有效（格式正确且连续）括号子串的长度。 解题过程 问题分析 有效括号字符串需满足： 每个左括号 '(' 必须有对应的右括号 ')'。 左括号必须在对应的右括号之前。 有效的子串必须是连续的。 动态规划定义 我们使用一个数组 dp ，其中 dp[i] 表示 以字符 s[i] 为结尾 的最长有效括号子串的长度。 关键点：有效子串必然以 ')' 结尾。因此，如果 s[i] 是 '('，那么以它结尾的子串不可能是有效的，即 dp[i] = 0 。 状态转移方程 我们只需要考虑 s[i] 是 ')' 的情况。这又分为两种子情况： 情况一： s[i-1] 是 '(' 字符串形如： ......() 。 此时， s[i] 的配对伙伴就是紧挨着它的 s[i-1] 。 因此，以 s[i] 结尾的最长有效子串，就是在 s[i-1] 之前已经形成的有效子串长度，再加上这对新配对的括号。 公式 ： dp[i] = dp[i-2] + 2 边界处理 ：如果 i-2 小于 0（即 i==1 ），则 dp[i-2] 视为 0。 情况二： s[i-1] 是 ')' 字符串形如： ......)) 。 这种情况更复杂。我们需要检查与当前 s[i] 配对的 '(' 是否存在。 首先，找到以 s[i-1] 结尾的有效子串的前一个字符。这个字符的位置是 i - dp[i-1] - 1 。 如果这个字符 s[i - dp[i-1] - 1] 存在且是 '('，那么它就能与当前的 s[i] 配对。 此时，我们成功配对了一对括号： dp[i] = dp[i-1] + 2 。 但是，这还不是全部。在成功配对的这对括号 之前 ，可能还存在一个更早的有效子串。我们需要把它们连接起来。 例如： ()(()) ，当 i=5 (最后一个字符)时，我们配对成功后，发现前面 i=0,1 位置还有一个 () 。我们需要把 () 和 (()) 连接起来。 这个更早的子串的长度就是 dp[i - dp[i-1] - 2] 。 综合公式 ： 如果 s[i - dp[i-1] - 1] == '(' ，则 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2] 边界处理 ：同样，如果 i - dp[i-1] - 2 小于 0，则对应的 dp 值视为 0。 计算顺序 由于 dp[i] 依赖于 dp[i-1] 、 dp[i-2] 等更早的状态，我们需要从左到右遍历字符串 s 。 示例推导 以 s = "()(())" 为例，初始化 dp 数组为全 0。 i=0 : s[0]='(' -> dp[0] = 0 i=1 : s[1]=')' , 且 s[0]='(' (情况一) -> dp[1] = dp[-1](视为0) + 2 = 2 i=2 : s[2]='(' -> dp[2] = 0 i=3 : s[3]='(' -> dp[3] = 0 i=4 : s[4]=')' , 且 s[3]='(' (情况一) -> dp[4] = dp[2] + 2 = 0 + 2 = 2 i=5 : s[5]=')' , 且 s[4]=')' (情况二)： 检查位置 i - dp[4] - 1 = 5 - 2 - 1 = 2 的字符 s[2] ，它是 '('，配对成功。 dp[5] = dp[4] + 2 + dp[2 - 1]? 让我们仔细计算： 基础部分： dp[4] + 2 = 2 + 2 = 4 。 连接前面的子串：前面的位置是 i - dp[4] - 2 = 5 - 2 - 2 = 1 。 dp[1] = 2 。 所以 dp[5] = 4 + 2 = 6 。 最终， dp 数组为 [0, 2, 0, 0, 2, 6] 。最大值为 6，即最长有效括号子串 "(())" 和前面的 "()" 连接成的 "()(())" ，长度为 6。 算法总结 初始化一个长度为 n 的 dp 数组，全部设为 0。 遍历 i 从 1 到 n-1 ： 如果 s[i] == ')' ： 如果 s[i-1] == '(' (情况一): dp[i] = (dp[i-2] if i >= 2 else 0) + 2 如果 s[i-1] == ')' (情况二) 且 i - dp[i-1] > 0 且 s[i - dp[i-1] - 1] == '(' : dp[i] = dp[i-1] + 2 + (dp[i - dp[i-1] - 2] if (i - dp[i-1]) >= 2 else 0) 最终答案是 dp 数组中的最大值。