❌ LeetCode 32 - 最长有效括号：动态规划思路错题分析

问题描述

LeetCode 32 题 - 最长有效括号要求我们找到给定字符串中由匹配括号组成的最长有效（格式正确且连续）括号子串的长度。

有效括号字符串的定义如下：

空字符串是有效括号字符串
如果s是有效括号字符串，那么(s)也是有效括号字符串
如果s和t都是有效括号字符串，那么st（它们的连接）也是有效括号字符串

示例输入输出：

示例 1:
输入: s = "(()"
输出: 2
解释: 最长有效括号子串是 "()"

示例 2:
输入: s = ")()())"
输出: 4
解释: 最长有效括号子串是 "()()"

示例 3:
输入: s = ""
输出: 0

约束条件：

0 <= s.length <= 3 * 10^4
s[i] 只包含 '(' 和 ')'

最初的错误解法

我最初尝试使用动态规划解决这个问题。我定义 dp[i] 表示以字符串 s 中第 i-1 个字符结尾的最长有效括号的长度，dp 数组的大小为 n+1（其中 n 是字符串长度），dp[0] 初始化为 0。

以下是我最初的解法（包含错误）：

// 错误代码片段
func longestValidParentheses_buggy(s string) int {
    n := len(s)
    dp := make([]int, n+1) // dp[i] 表示以 s[i-1] 结尾的最长有效括号长度

    for i := 1; i < n; i++ { // 遍历 s[1] 到 s[n-1]
        // 当前考虑的字符是 s[i]，对应 dp[i+1]
        if s[i] == ')' {
            if s[i-1] == '(' { // 情况 1: ...()
                // s[i-2] 结尾的 LVP + "()"
                // 如果 i-2 < 0, dp[i-1] (即 dp[i-2+1]) 会是 dp[-1+1]=dp[0]=0
                dp[i+1] = dp[i-1] + 2
            } else if s[i-1] == ')' { // 情况 2: ...))
                // j 指向 s[i-1] 对应 LVP (长度 dp[i]) 前一个字符
                // dp[i] 是以 s[i-1] 结尾的 LVP 长度
                j := i - dp[i] - 1
                if j >= 0 && s[j] == '(' { // 如果 s[j] 是 '('，形成 s[j]...s[i] 的匹配
                    // ❌ 错误点：状态转移逻辑错误
                    dp[i+1] = dp[j] + 1
                }
            }
        }
    }

    ans := 0
    for k := 0; k <= n; k++ {
        ans = max(ans, dp[k])
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

这个解法在以下测试用例中失败：

1
2
3

输入: s = ")()())"
预期输出: 4
实际输出: 2

错误分析

主要的错误出现在处理 s[i] == ')' 并且 s[i-1] == ')' 的情况，即形如 ...)) 的子串。具体来说，错误发生在状态转移方程的计算中。

让我们通过一个具体的例子来分析这个错误：

对于字符串 ")()())"，我们逐步执行动态规划：

dp[0] = 0（初始化）
对于 s[0] = ')': 不可能形成有效括号，dp[1] = 0
对于 s[1] = '(': 不可能以左括号结尾，dp[2] = 0
对于 s[2] = ')': 与前一个字符 s[1] = '(' 匹配，dp[3] = dp[1] + 2 = 0 + 2 = 2
对于 s[3] = '(': 不可能以左括号结尾，dp[4] = 0
对于 s[4] = ')': 与前一个字符 s[3] = '(' 匹配，dp[5] = dp[3] + 2 = 2 + 2 = 4
对于 s[5] = ')': 需要检查是否可以与某个左括号匹配

在第 7 步，也就是处理字符串最后一个字符 ) 时，我们需要考虑它能否与某个左括号匹配。这时：

s[5] = ')'
s[4] = ')'（前一个字符也是右括号）
dp[5] = 4（表示以 s[4] 结尾的最长有效括号长度）
j = 5 - 4 - 1 = 0（j 是指向当前有效括号子串前一个位置的索引）
s[j] = s[0] = ')'（不是左括号）

在这个例子中，由于 s[j] 不是左括号，所以不会形成新的匹配。但这并不是我想要关注的错误。

关键错误分析：

当 s[i] == ')' 且 s[i-1] == ')' 且 j >= 0 且 s[j] == '(' 时，我错误地将状态转移方程写成了 dp[i+1] = dp[j] + 1。

这个错误的状态转移公式有两个问题：

+1 是错误的，应该是 +2，因为我们需要加上 s[j] 和 s[i] 这两个新匹配的括号。
没有考虑到 s[j+1...i-1] 这部分已经形成的有效括号长度，即 dp[i]。

正确的思路是：新形成的有效括号子串长度应该是三部分之和：

dp[j]：以 s[j-1] 结尾的最长有效括号长度（可能连接到新匹配前面的部分）
+ dp[i]：以 s[i-1] 结尾的最长有效括号长度（s[j+1...i-1] 的部分）
+ 2：s[j] 和 s[i] 这两个新匹配的括号

正确的动态规划思路

要解决最长有效括号问题，我们可以使用动态规划来追踪以每个位置结尾的最长有效括号子串长度。下面详细讲解思路：

状态定义

定义 dp[i] 表示以字符串 s 中索引 i-1 的字符结尾的最长有效括号的长度
使用 dp 数组大小为 n+1，其中 dp[0]=0 表示空串

状态初始化

dp[0] = 0（空串）
对于所有的 i ≥ 1，初始时 dp[i] = 0

状态转移方程

由于有效括号子串必须以右括号 ')' 结尾，所以我们只需考虑 s[i-1] = ')' 的情况。根据前一个字符，有两种主要情况：

情况一：s[i-1] = ')' 且 s[i-2] = '(' (形如 ...())
- 这种情况下，s[i-2] 和 s[i-1] 构成一对匹配的括号 "()"
- 如果 i-3 位置之前也有有效括号子串，需要加上它的长度
- 状态转移方程：dp[i] = dp[i-2] + 2
- 其中 dp[i-2] 是以 s[i-3] 结尾的最长有效括号长度
- +2 表示新增了一对匹配的括号
情况二：s[i-1] = ')' 且 s[i-2] = ')' (形如 ...)))
- 这种情况更复杂，我们需要找到与 s[i-1] 匹配的左括号
- 首先，我们知道以 s[i-2] 结尾的最长有效括号长度为 dp[i-1]
- 这意味着子串 s[(i-1-dp[i-1])...(i-2)] 是有效的
- 我们需要查看这个子串之前的字符 s[i-1-dp[i-1]-1]，记为 s[j]
- 如果 s[j] = '('，那么它可以与 s[i-1] 匹配
- 这样会形成一个新的有效括号子串，长度为：
  - dp[i-1]：以 s[i-2] 结尾的有效括号长度
  - +2：新增的一对匹配括号 s[j] 和 s[i-1]
  - +dp[j]：以 s[j-1] 结尾的有效括号长度（如果存在）
- 状态转移方程：dp[i] = dp[i-1] + 2 + dp[j]，其中 j = i-1-dp[i-1]-1

求解过程

初始化 dp 数组，所有元素为 0
从左到右遍历字符串，只有当 s[i] = ')' 时才可能更新 dp[i+1]
根据不同情况应用状态转移方程
遍历完成后，dp 数组中的最大值即为答案

图解状态转移

举例说明两种情况的状态转移：

情况一：当前字符与前一个字符形成 "()"

s = "......()"
           ^^
        i-2 i-1

dp[i] = dp[i-2] + 2

情况二：当前字符与更前面的字符形成匹配

s = "...(.......)"
        ^       ^
        j       i-1

其中 j = i-1-dp[i-1]-1
dp[i] = dp[i-1] + 2 + dp[j]

注意，在情况二中，dp[i-1] 表示以 s[i-2] 结尾的有效括号的长度。这个有效括号子串的起始位置是 i-1-dp[i-1]，因此 j 是该子串前一个位置的索引。

改进的解决方案

根据上述分析，我们需要修正状态转移方程。以下是改进后的代码：

// 修正后的核心部分
if s[i-1] == ')' {
    j := i - dp[i] - 1 // dp[i] 是以 s[i-1] 结尾的LVP的长度
    if j >= 0 && s[j] == '(' {
        // 修正点：正确的状态转移逻辑
        dp[i+1] = dp[i] + 2 + dp[j]
    }
}

完整的修正代码如下：

package main

func longestValidParentheses(s string) int {
    n := len(s)
    if n < 2 {
        return 0
    }

    // dp[k] 表示以 s[k-1] 结尾的最长有效括号的长度
    // 为了方便处理边界，dp 数组大小为 n+1，dp[0] 始终为 0
    // 循环中 i 代表当前字符 s[i] 的索引，更新的是 dp[i+1]
    dp := make([]int, n+1)

    for i := 1; i < n; i++ { // 遍历 s[1] 到 s[n-1]
        if s[i] == ')' {
            if s[i-1] == '(' { // 情况 1: 字符串形如 "...()"
                // dp[i-1] 是以 s[i-2] 结尾的LVP长度
                dp[i+1] = dp[i-1] + 2
            } else { // 情况 2: 字符串形如 "...))"
                // s[i-1] 是 ')'
                // dp[i] 是以 s[i-1] 结尾的LVP长度
                // j 是 s[i-1] 结尾的LVP前一个字符的索引
                j := i - dp[i] - 1
                if j >= 0 && s[j] == '(' {
                    // s[j] 是 '(', s[i] 是 ')'
                    // 以 s[i] 结尾的LVP = (以 s[i-1] 结尾的LVP) + s[j]...s[i] + (以 s[j-1] 结尾的LVP)
                    // 长度 = dp[i] (s[j+1...i-1]部分) + 2 (s[j]和s[i]) + dp[j] (以s[j-1]结尾的LVP)
                    dp[i+1] = dp[i] + 2 + dp[j]
                }
            }
        }
        // 如果 s[i] == '('，dp[i+1] 保持为 0，因为有效括号子串不可能以 '(' 结尾
    }

    ans := 0
    for k := 0; k <= n; k++ {
        if dp[k] > ans {
            ans = dp[k]
        }
    }
    return ans
}

为什么这个解法可以工作

修正后的解法正确考虑了所有情况：

当前字符 s[i] = ')' 且前一个字符 s[i-1] = '(' 时：
- 直接形成一对新的有效括号 ()
- 加上之前可能已经形成的有效括号子串长度：dp[i+1] = dp[i-1] + 2
当前字符 s[i] = ')' 且前一个字符 s[i-1] = ')' 时：
- 前一个位置已经形成了长度为 dp[i] 的有效括号子串
- 需要找到这个子串前一个位置 j = i - dp[i] - 1
- 如果 s[j] = '('，则 s[j] 和 s[i] 形成新的匹配，同时连接了三部分：
  - 以 s[j-1] 结尾的有效括号子串：dp[j]
  - s[j] 和 s[i] 形成的新匹配：+2
  - 中间部分 s[j+1...i-1] 的有效括号子串：dp[i]

这样，我们正确计算了以每个位置结尾的最长有效括号长度，最终结果就是其中的最大值。

另一种解法：使用栈

除了动态规划，我们还可以使用栈来解决这个问题。栈方法的核心思想是：用栈来匹配括号，并计算匹配后形成的有效括号子串的长度。

栈方法的算法思路

初始化栈，先放入一个哨兵元素 -1（用于处理边界情况）
遍历字符串中的每个字符：
- 如果是左括号 '('，将其索引入栈
- 如果是右括号 ')'：
  - 先弹出栈顶元素（可能是左括号的索引或前一个无法匹配的右括号的索引）
  - 如果此时栈为空，将当前右括号的索引入栈（表示这是一个无法匹配的右括号）
  - 如果栈不为空，计算当前位置与栈顶元素的距离，更新最长有效括号长度

栈方法代码实现

func longestValidParenthesesUsingStack(s string) int {
    maxLen := 0
    stack := []int{-1} // 栈底放一个-1作为哨兵，方便计算长度

    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            stack = append(stack, i) // 左括号，索引入栈
        } else { // s[i] == ')'
            stack = stack[:len(stack)-1] // 弹出栈顶，可能是左括号或前一个无法匹配的右括号

            if len(stack) == 0 {
                stack = append(stack, i) // 栈为空，当前右括号无法匹配，入栈作为新的起始点
            } else {
                // 计算当前有效子串的长度：当前位置 - 栈顶元素
                // 栈顶元素是上一个无法匹配的位置（可能是右括号，也可能是初始的-1）
                maxLen = max(maxLen, i - stack[len(stack)-1])
            }
        }
    }

    return maxLen
}

栈方法的工作原理示例

以输入 ")()())" 为例，我们跟踪栈的变化：

初始化：stack = [-1]
处理 s[0] = ')':
- 弹出 -1，栈为空
- 将 0 入栈：stack = [0]
处理 s[1] = '(':
- 将 1 入栈：stack = [0, 1]
处理 s[2] = ')':
- 弹出 1，栈不为空
- 计算长度：2 - 0 = 2，更新 maxLen = 2
- 当前栈：stack = [0]
处理 s[3] = '(':
- 将 3 入栈：stack = [0, 3]
处理 s[4] = ')':
- 弹出 3，栈不为空
- 计算长度：4 - 0 = 4，更新 maxLen = 4
- 当前栈：stack = [0]
处理 s[5] = ')':
- 弹出 0，栈为空
- 将 5 入栈：stack = [5]

最终 maxLen = 4，这是正确答案。

两种方法的比较

方面	动态规划	栈方法
时间复杂度	O(n)	O(n)
空间复杂度	O(n)	O(n)
实现难度	中等（状态转移需要仔细推导）	简单（括号匹配的典型应用）
思路理解	需要理解状态定义和状态转移	直观，基于括号匹配
代码量	中等	较少
适用性	类似的子串问题	括号相关问题

学习总结

通过分析这个错误，我学到了以下重要教训：

状态定义的精确理解：在动态规划中，准确理解状态的定义至关重要。在这个问题中，dp[k] 表示以 s[k-1] 结尾的最长有效括号长度，需要清晰理解这个定义。
完整的状态转移分析：在推导状态转移方程时，必须考虑所有可能的组成部分。对于括号匹配这类问题，新形成的有效括号子串可能由多个部分组成，需要全面分析各部分的贡献。
细心处理索引和边界条件：动态规划中的索引处理尤为重要，特别是当状态数组和原始数据的索引有偏移时。在这个问题中，dp[i+1] 对应 s[i]，这种对应关系需要时刻牢记。
可视化辅助理解：对于复杂的状态转移，可以通过画图或具体示例来验证思路。例如，对于 ...)) 模式，可以画出不同情况下的括号组合和对应的 dp 值是如何累加的。
多种解法对比学习：同一个问题往往有多种解法。动态规划和栈方法各有优缺点，通过对比学习，可以加深对问题的理解，也有助于在实际应用中选择最合适的方法。
测试关键用例：针对特定的状态转移逻辑，构造关键测试用例进行验证非常重要。例如，对于这个问题，应该特别测试包含 ...))、...() 等模式的字符串。

这个错误提醒我，在动态规划问题中，即使大方向正确，状态转移方程中的一个小细节偏差也可能导致完全错误的结果。细心推导和验证每一种情况是解决复杂动态规划问题的关键。