最长有效括号匹配子串的动态规划解法 我将为你讲解 最长有效括号匹配子串的动态规划解法 。这个题目是求一个只包含字符 '(' 和 ')' 的字符串中，最长的有效（格式正确且连续）括号子串的长度。 题目描述 给定一个仅由字符 '(' 和 ')' 组成的字符串 s ，请你找出其中最长的有效括号子串的长度。所谓“有效括号子串”是指： 每个左括号 '(' 必须有对应的右括号 ')' 与之匹配。 左括号必须在对应的右括号之前。 括号之间必须正确嵌套，且连续不断开。 例如： 输入： "(()" ，输出： 2 （最长有效子串是 "()" ） 输入： ")()())" ，输出： 4 （最长有效子串是 "()()" ） 输入： "" ，输出： 0 解题过程 我们先明确目标：用 动态规划 来求解这个问题。动态规划的核心是定义状态，找到状态转移方程，并用已知的状态推导未知的状态。 步骤 1: 定义状态 我们定义一个数组 dp ，其中 dp[i] 表示 以字符串 s 中第 i 个字符结尾的最长有效括号子串的长度 。注意这里的“以第 i 个字符结尾”很重要，它保证了子串的连续性。 例如，对于 s = ")()())" ： 下标从 0 开始， s[0] = ')' ， dp[0] = 0 （因为以 ')' 结尾不可能形成有效子串）。 s[1] = '(' ， dp[1] = 0 （以 '(' 结尾也不可能，因为缺右括号）。 我们需要计算所有 dp[i] ，然后取其中的最大值，即为最终答案。 步骤 2: 初始化边界 首先，如果字符串为空或长度为 1，显然最长有效括号长度为 0。我们可以初始化 dp 所有元素为 0。 步骤 3: 状态转移方程 我们考虑如何从已知的 dp[0...i-1] 推导出 dp[i] 。分两种情况讨论： 情况 1：当前字符 s[i] 是 '(' 此时，以 '(' 结尾不可能形成有效括号串，因为有效子串必须以 ')' 结尾才能完成匹配。所以： 情况 2：当前字符 s[i] 是 ')' 这种情况较复杂，我们需要考虑与当前 ')' 匹配的左括号在哪里。又可以分为两个子情况： 子情况 2.1：前一个字符是 '(' ，即 s[i-1] = '(' 这时， s[i-1] 和 s[i] 正好组成一对有效括号 "()" 。 那么，以 s[i] 结尾的最长有效子串至少是 2。 另外，还需要考虑在这对括号之前是否还有有效括号串，可以连接起来。即： 如果 i-2 < 0 ，则 dp[i-2] 视为 0。 例如： s = "()" ， i=1 ： s[1]=')' ， s[0]='(' ， dp[1] = 2 + dp[-1] ， dp[-1] 视为 0，所以 dp[1]=2 。 子情况 2.2：前一个字符是 ')' ，即 s[i-1] = ')' 这时， s[i] 是 ')' ，我们需要找到与它匹配的左括号的位置。这个位置应该是： 解释： dp[i-1] 是以 s[i-1] 结尾的最长有效括号长度，那么从 i-1 往前数 dp[i-1] 个字符，这个子串是以 s[i-1] 结尾的有效括号串。这个子串的前一个字符（即位置 j ）可能是与 s[i] 匹配的左括号。 如果 j >= 0 且 s[j] = '(' ，说明我们找到了匹配的左括号。那么当前有效子串长度为： 但还没完！在 s[j] 之前可能还有有效括号串，可以连起来。所以总长度要加上 dp[j-1] （即 j 之前的有效长度）： 如果 j-1 < 0 ，则 dp[j-1] 视为 0。 例如： s = "()(())" ，计算 i=5 （最后一个 ')' ）： s[5]=')' ， s[4]=')' ， dp[4]=2 （因为 s[3]='(' ， s[4]=')' 组成 "()" ）。 计算 j = 5 - dp[4] - 1 = 5 - 2 - 1 = 2 。 s[2]='(' ，匹配成功。 那么 dp[5] = dp[4] + 2 + dp[1] 。 dp[1]=0 （因为 s[1]=')' ），所以 dp[5]=4 。 但实际上， "()(())" 整个是有效的，长度为 6。这里计算的是 4，对吗？我们检查： s[0]='(' ， s[1]=')' 是独立的 "()" ， s[2] 到 s[5] 是 "(())" 长度 4，这两段是独立的，不能连成整个 "()(())" ，因为 s[1] 和 s[2] 之间是断开的。所以 dp[5]=4 正确。整个字符串的最长有效子串长度实际上是 6（即 "()(())" 整个），这会在 dp[5] 中计算吗？注意， dp[5] 是以 s[5] 结尾的最长有效子串长度，是 4。但整个字符串的有效子串长度应该是 6，这是怎么来的？其实是因为 s[0] 到 s[5] 整体有效，但我们计算 dp[5] 时， j=2 ， dp[j-1] = dp[1] = 0 ，所以没有加上前面的 "()" 。但当我们计算 dp[5] 时， j-1=1 ， dp[1]=0 ，确实没有连接上。等等，这里需要验证整个字符串是否真的有效。 "()(())" 是有效的，但我们的 dp[5] 算出 4，说明整个串没有被识别为一个整体。我们需要更仔细地分析。 我们重新仔细推导这个例子： s = "()(())" ，下标 0~5。 先手算一下：有效括号子串是 "()" （下标 0~1）和 "(())" （下标 2~5），以及整个 "()(())" （下标 0~5）。所以最长长度是 6。 用我们的动态规划计算： dp[0]=0 （'(' 结尾） dp[1]=2 （因为 s[0]='(' ， s[1]=')' ，且 i=1 时 dp[1] = 2 + dp[-1] = 2 ） dp[2]=0 （'(' 结尾） dp[3]=0 （'(' 结尾） dp[4]=2 （因为 s[3]='(' ， s[4]=')' ， dp[4]=2+dp[2]=2 ） 现在计算 dp[5] ： s[5]=')' ， s[4]=')' ，属于子情况 2.2。 j = 5 - dp[4] - 1 = 5 - 2 - 1 = 2 s[2] = '(' ，匹配成功。 所以 dp[5] = dp[4] + 2 + dp[1] = 2 + 2 + 2 = 6 。 这里 dp[1]=2 加上了，所以连接了前面的 "()" 。因此 dp[5]=6 正确。 所以状态转移公式正确。 步骤 4: 算法流程 如果字符串长度 n < 2 ，返回 0。 创建 dp 数组，长度 n ，初始化为 0。 从 i=1 开始遍历到 n-1 ： 如果 s[i] = '(' ， dp[i] = 0 。 如果 s[i] = ')' ： 如果 s[i-1] = '(' ，则 dp[i] = 2 + (dp[i-2] if i>=2 else 0) 。 如果 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) 。 遍历过程中，记录 dp[i] 的最大值，即为结果。 步骤 5: 举例演算 以 s = ")()())" 为例，长度为 6。 初始化 dp = [0,0,0,0,0,0] ， max_len = 0 。 i=0 ： s[0]=')' ，但 i=0 是第一个字符，前面没有字符，所以 dp[0]=0 。 i=1 ： s[1]='(' ， dp[1]=0 。 i=2 ： s[2]=')' ，且 s[1]='(' ，属于子情况 2.1。 dp[2] = 2 + dp[0] = 2+0=2 。 max_len=2 。 i=3 ： s[3]='(' ， dp[3]=0 。 i=4 ： s[4]=')' ，且 s[3]='(' ，属于子情况 2.1。 dp[4] = 2 + dp[2] = 2+2=4 。 max_len=4 。 i=5 ： s[5]=')' ，且 s[4]=')' ，属于子情况 2.2。 dp[4]=4 ， j = 5 - 4 - 1 = 0 。 s[0]=')' ，不是 '(' ，所以匹配失败， dp[5]=0 。 最终 max_len=4 ，最长有效括号子串是 "()()" （下标 1~4），长度为 4。 步骤 6: 时间复杂度与空间复杂度 时间复杂度：O(n)，只需遍历一次字符串。 空间复杂度：O(n)，用于存储 dp 数组。 总结 这个动态规划解法的关键在于定义 dp[i] 为以 s[i] 结尾的最长有效括号子串长度，然后通过当前字符和之前字符的关系，分情况讨论，推导出状态转移方程。最后，取所有 dp[i] 中的最大值即为答案。 这个解法比暴力法（O(n³)）和栈解法（O(n) 空间 O(n)）在思路上更直接地体现了动态规划的思想，是解决此类区间最值问题的典型方法。