最长有效括号如何用动态规划求解？dp[i] 为什么表示以 i 结尾的长度？

简化版

最长有效括号可以定义 dp[i] 为以 s[i] 结尾的最长有效括号长度。只有当 s[i] == ')' 时才可能形成有效串，根据前一个字符是 '(' 还是 ')' 分两类转移，并尝试把前面相邻的有效段拼接起来。

详细版

如果 s[i-1] == '('，那么 ...() 形成一对，dp[i] = dp[i-2] + 2。如果 s[i-1] == ')'，说明前面可能已经有一段有效括号，设它长度为 dp[i-1]，再看这段之前的位置 pre = i - dp[i-1] - 1 是否是 '('，如果是，就能把它包起来，并连接 pre 前面的有效段。

转移时要特别注意下标越界。时间复杂度 O(n)，空间复杂度 O(n)。这题也能用栈做，但 DP 写法更能体现“以当前位置结尾”的状态设计。

完整版教学

一、为什么状态要定义成“以 i 结尾”

最长有效括号问的是一个子串长度，子串必须连续。定义成“前 i 个字符里的最大值”不方便判断当前字符是否能接上前面的连续有效段；定义成“以 i 结尾”就能直接讨论当前结尾是否有效。

s = ") ( ) ( ( ) )"
idx 0 1 2 3 4 5 6

当 i=6 时，我们关心的是以第 6 位 ')' 结尾能形成多长，而不是整个前缀里曾经出现过多长。

二、只有右括号才会产生新答案

有效括号串一定以 ')' 结尾。如果 s[i] == '('，它不可能作为某段有效括号的最后一个字符，所以 dp[i]=0。

当前字符	是否可能结尾	原因
`'('`	不可能	缺少右括号闭合
`')'`	可能	可以闭合某个左括号

记忆钩子：括号 DP 先看结尾，左括号负责等待，右括号负责结算。

这个判断能减少一半讨论，也能防止你对 '(' 写出无意义转移。

三、情况一：直接出现 `()`

如果 s[i] == ')' 且 s[i-1] == '('，那么最后两个字符组成一对。

... ( )
    i-1 i

此时还要接上 i-2 结尾的有效长度：

dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2

例如 s="()()"，当 i=3 时，最后两位是 ()，前面 dp[1]=2 可以拼上，所以 dp[3]=4。

四、情况二：用一个左括号包住前面的有效段

如果 s[i-1] == ')'，前一位已经可能是一段有效括号的结尾。设这段长度是 dp[i-1]，那么它的前一个位置是：

pre = i - dp[i - 1] - 1

如果 pre >= 0 且 s[pre] == '('，就能形成：

(  [一段有效括号]  )
pre             i

转移为：

dp[i] = dp[i - 1] + 2 + (pre >= 1 ? dp[pre - 1] : 0)

最后一项是为了连接更前面的连续有效段。

五、用例子推演为什么要拼接前段

看字符串：

s = "()(())"
idx 0 1 2 3 4 5

当 i=5 时，dp[4]=2 对应 "()"，pre = 5 - 2 - 1 = 2，s[2]='('，所以可以包成 "(())"，长度 4。再看 pre-1=1，dp[1]=2，说明前面还有 "()" 可以拼接，总长度是 6。

如果不加 dp[pre-1]，答案会停在 4，漏掉连续拼接。

六、代码模板

int longestValidParentheses(String s) {
    int n = s.length();
    int[] dp = new int[n];
    int ans = 0;
    for (int i = 1; i < n; i++) {
        if (s.charAt(i) == ')') {
            if (s.charAt(i - 1) == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else {
                int pre = i - dp[i - 1] - 1;
                if (pre >= 0 && s.charAt(pre) == '(') {
                    dp[i] = dp[i - 1] + 2 + (pre >= 1 ? dp[pre - 1] : 0);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
    }
    return ans;
}

下标 pre 是这题最容易写错的位置。它不是 i - dp[i-1]，因为还要再往前找一个可能匹配当前 ')' 的左括号。

七、常见误区与追问

误区：把 dp[i] 定义成前缀最大值。 前缀最大值不能直接判断当前字符能否连续接上。
误区：忘记连接 dp[pre-1]。 会漏掉 "()(())" 这种前后连续有效段。
误区：pre 下标少减 1。 前一段有效括号已经占了 dp[i-1] 个字符，还要再往前找匹配左括号。
追问：栈解法和 DP 解法区别是什么？ 栈维护未匹配下标，DP维护以每个位置结尾的连续长度。
追问：空间能优化吗？ DP 需要访问多个历史位置，不像普通线性 DP 那样容易压缩。
追问：为什么 '(' 位置 dp 是 0？ 有效括号串不能以左括号结尾。

八、加强记忆

最长有效括号的抓手是“右括号结算”。dp[i] 只表示以 i 结尾的长度，遇到 () 就接 dp[i-2]，遇到 )) 就跳过前一段有效串去找配对的左括号，再把更前面的有效串拼上。记住 pre = i - dp[i-1] - 1，这题的骨架就立住了。

简化版

详细版