一道“看似简单”的括号题为什么那么多人在上面翻车先说一个我印象特别深的面试场景候选人看到题目里写着“括号子串”眼睛一亮立刻开始在白板上写括号配对判断的代码。他先维护一个计数器遇到(加一遇到)减一如果某个时刻计数器归零就认为这一段合法最后输出最大长度。写完后面试官问了一句“那)()())这个输入你的答案是多少”候选人愣了一下因为他统计出来的“合法对”是 3但题目要的是连续的、有效的括号子串长度正确答案是 4。这个细节就是动态规划解法里最核心、也最容易被人忽略的地方。最长有效括号子串问题是动态规划题单里一个绕不开的经典。它既不像矩阵路径那样有明确的二维表格也不像背包问题那样有清晰的“选或不选”它的状态转移完全依靠字符串的局部结构某个位置是否是)以及它前面的字符和更前面的子串状态。很多人在洛谷、力扣上刷到这类题时第一反应是用栈做括号匹配但对动态规划的解法和它背后的建模思路并不清楚。这篇文章我想系统地把这几个问题讲透为什么配对计数在这里失效怎么设计dp[i]这个状态转移方程每一条分别处理什么结构以及你什么时候该选栈解法、什么时候该选双指针解法。这篇文章适合这几类人看准备算法面试的求职者想系统理解序列型动态规划建模的入门者还有需要处理括号合法性校验问题的工程开发。我说得直接一点——如果你能把这道题的dp推导过程完整复述出来你能想明白“为什么dp[i]非得表示‘以第 i 个字符结尾的最长有效子串长度’”那你对动态规划的运用能力就已经超过大多数只背模板的候选人了。1. 从“配对计数”到“连续区间”这道题的难点不在括号本身很多人拿到这道题第一反应是括号匹配不是很简单吗栈一压一弹就完事了。这话对也不对。如果题目是“判断整个字符串是不是合法括号串”栈解法确实一秒搞定。但题目说的是“最长有效子串”拆开来看有三个限定词最长、有效、子串。前两个好理解第三个才是真正的坑。子串意味着连续性。()()是长度为 4 的有效子串(())是长度为 4 的有效子串但把整个字符串拆成不连续的几个合法片段再拼起来这种“局部合法”不能直接相加。比如)()())全串中确实存在 3 对合法括号但它们不连续地位于同一个区间内索引 1 到 2 是()索引 3 到 4 是()可是第 0 位的)和最后第 5 位的)把整个串切断了你没法把这两段拼成一个更长的合法区间。1.1 暴力枚举为什么不可行先看清复杂度上限如果没学过动态规划最朴素的思路是枚举所有子串。假设字符串长度是 n子串有 O(n²) 个对每个子串做一次合法性校验需要 O(n) 的时间总复杂度 O(n³)。n 是 100 的时候勉强能算n 是 10⁵ 的时候就是天文数字。如果把合法性校验优化成前缀和做复杂度能降到 O(n²)。具体做法是把(记为 1)记为 -1用前缀和数组快速判断某个区间内括号是否完全配对且中途从未出现负值。这个方案比 O(n³) 强了很多但依然扛不住大数据而且“中途从未出现负值”这个条件本身也不好用前缀和直接判断需要额外预处理最小值。所以无论怎么优化暴力这道题的出路都是线性做法要么用动态规划要么用栈要么用双指针。1.2 一个输入带上三个反例先把直觉校准我在自己刷题时试过一组特别好的测试输入用来纠正对“连续有效子串”的直觉() - 2 (()) - 4 ()() - 4 (() - 2 )()()) - 4 ()(()) - 6()(())这个例子很有迷惑性。它从左往右看是()和(())拼在一起中间没有多余字符所以整个长度 6 是有效子串。但()())(()这种中间被)(截断的就不能把左边 4 和右边 2 相加因为中间断开的部分破坏了连续性和合法性。我见过不少人栽在这里他们把字符串拆成若干段每段内部合法然后试图把相邻的段加起来结果忽略了“段与段之间如果有非法字符整段就不连续”。记住一个判断口诀真正的有效括号子串从左到右任意前缀的)数量都不能超过(数量且整个子串最后)数量恰好等于(数量。这个性质是后面所有解法的理论根基。2. dp[i] 的定义以“结尾”还是以“开头”做状态差之毫厘谬以千里进入正题讲动态规划解法。先说结论这道题的状态定义是dp[i] 表示字符串 s 中以 s[i] 作为最后一个字符的最长有效括号子串的长度。注意是“以 i 结尾”不是“前 i 个字符中能构成的最长有效括号子串的长度”。这两个定义看起来差不多但转移方程的难度完全不同。如果你定义dp[i] 前 i 个字符中的最长有效括号子串长度那你在推导dp[i1]的时候得回看整个前面的子串去判断新增的一个字符能不能把某个已有的合法子串“接长”这几乎无法用常数时间完成。相反用“以 i 结尾”定义每个位置的状态只跟它前面有限的几个位置相关严格满足了动态规划“无后效性”的要求。为了让你彻底理解为什么必须这么定义我们先看一个反例。假设s ()()如果定义dp[i]为“前 i 个字符组成的前缀中的最长有效括号子串长度”那么前 4 个字符的答案就是 4没问题。但如果s ()(()前 3 个字符的答案是 2前 5 个字符的答案还是 2。你会发现前缀定义下dp的值在大多数位置保持不变只有遇到“恰好结束一个合法块”的位置才会跳变。这种跳变让状态之间的关联变得很不规则。而“以 i 结尾”的定义下只要s[i]是(dp[i]就必定是 0因为一个合法的括号子串不可能以左括号结尾这个清晰的归零逻辑是后续所有推导的基础。2.1 为什么dp[i]只在s[i] )时才有意义这其实是整个推导里最容易被忽略的点。一个合法的括号子串最后一个字符必然是)。所以如果你扫描到(直接让dp[i] 0不需要做任何判断。这是所有序列型括号 DP 的默认规则。而当s[i] )时又分成两种情况前一个字符是(或者前一个字符也是)。这两种情况对应着有效括号子串的两种拼接方式“并列拼接”和“嵌套拼接”。下面详细拆开讲。2.2 第一条转移方程s[i-1] (时的并列拼接如果s[i-1]是(而s[i]是)那这两个字符本身就构成了一个长度为 2 的合法子串()。问题是这个()前面紧挨着的部分是什么如果前面那段也是合法的有效括号子串那么整段可以连起来。举例说明s ( ) ( ) index 0 1 2 3 4当i 3时s[1](s[2])s[3](s[4])。此时s[3]是(s[4]是)满足“前一个字符是(”的条件。那么以索引 4 结尾的最长有效子串至少是s[3:5]这个长度为 2 的()。再看s[2]是)而dp[2]表示以索引 2 结尾的最长有效子串长度是 2因为s[1:3] ()。这两个合法块是连续紧挨着的所以可以拼接成()()长度就是dp[2] 2 4。归纳成公式就是dp[i] dp[i-2] 2 当 s[i] ) 且 s[i-1] (注意这里dp[i-2]可能是 0表示()前面没有有效字符那么答案就是 2没有问题。2.3 第二条转移方程s[i-1] )时的嵌套拼接这是大多数人写不出来的那一步。如果s[i]是)s[i-1]也是)说明当前要匹配的不是紧挨着的那个(,而是一个更长串内部的右括号。想象一个嵌套结构(())。最后一个)要匹配的是字符串最开头的那个(中间隔着( )这个长度为 2 的合法子串。设dp[i-1]为以i-1结尾的最长有效括号子串长度。既然s[i-1]是)那么与它配对的左括号应该在j i - dp[i-1] - 1这个位置。如果s[j]恰好是(那它就能跟s[i]配对构成一个更大一层的嵌套。此时以i结尾的有效子串长度为dp[i] dp[i-1] 2但还没完。s[j]这个左括号前面紧挨着的如果也是一段合法子串还可以继续拼接。于是最终公式变成dp[i] dp[i-1] 2 dp[j-1]其中j-1 i - dp[i-1] - 2。这个公式是整道题的核心我用一个具体例子帮你看懂。假设s ( ) ( ( ) ) index 0 1 2 3 4 5 6我们计算i 6时的dp[6]。s[6] )s[5] )属于第二种情况。先算dp[5]以索引 5 结尾的最长有效子串是( )长度 2。于是j 6 - 2 - 1 3s[3] (匹配成功。s[3]和s[6]配对后内层dp[5] 2加上新配对 2得到 4。再看s[3]前面s[2] )而dp[2] 2s[0]和s[1]是()。这又是个合法的并列块所以可以继续加上dp[2] 2最终dp[6] 2 2 2 6。这正好对应()(())这个整体长度为 6 的合法子串。我把两条转移方程汇总一下写成代码最直观def longest_valid_parentheses(s: str) - int: n len(s) if n 2: return 0 dp [0] * n ans 0 for i in range(1, n): if s[i] ): if s[i-1] (: dp[i] (dp[i-2] if i 2 else 0) 2 else: # s[i-1] ) # 找到与 s[i] 配对的左括号候选位置 j j i - dp[i-1] - 1 if j 0 and s[j] (: dp[i] dp[i-1] 2 if j 1: dp[i] dp[j-1] ans max(ans, dp[i]) return ans这段代码应该是你脑子里最基础的模板之后无论遇到什么变种都从它开始改。3. 边界条件与代码实现的细节复盘差一个索引就报错动态规划题 80% 的 bug 出在下标越界上这道题尤其明显。我梳理了几个高频出错点每个都附带具体案例你在自己实现时对照着检查。3.1 回跳索引时的越界处理看第一条转移方程里的dp[i-2]。当i 1时i-2 -1直接越界。要意识到“s[i-1] (且s[i] )”这组配对至少需要两个字符所以i从 1 起步但dp[i-2]仍然可能落在 -1 上。处理办法很简单dp[i] (dp[i-2] if i 2 else 0) 2。再看第二条转移方程里的j。j i - dp[i-1] - 1其中dp[i-1]可能很大甚至达到i-1本身。这种情况下j会变成负数。比如s ())(())这个例子我不展开算你只需要记住j必须检查j 0且s[j] (两个条件缺一不可。我见过太多人漏掉j 0直接取s[j]运行时报 IndexError。同样dp[j-1]也要看j 1才取因为当j 0时j-1 -1越界。3.2 为什么无效位置的 dp 必须保持为 0我在刚开始写这题时犯过一个很隐蔽的错误我在遇到s[i] )但既匹配不上、也找不到左括号时给dp[i]赋了一个默认值比如dp[i-1]。这导致后续计算把一些非法片段拼接了起来结果错误地偏大。正确的做法是初始化数组全为 0s[i] (时直接跳过保持 0s[i] )但第二条转移条件不满足时也保持 0。可以这么理解dp[i] 存的是“以第 i 个字符结尾的有效子串长度”如果第 i 个字符无法成为某个合法子串的结尾那这个值就一定是 0不能继承前面的任何状态。举一个典型例子s ()())。索引 3 是)s[2](但s[3])它们能配对所以dp[3] 2。索引 4 是)此时s[3])dp[3]2于是j 4 - 2 - 1 1s[1](配对成功看起来dp[4] dp[3] 2 dp[0] 2 2 0 4。但实际上以索引 4 结尾的有效子串长度应该是 0因为s[1:5] ())的字符序列是( ) )不合法。这里的关键在于s[1]这个左括号前面紧挨着索引 0 的字符是()吗不是。我用j-1时取的是dp[0]而dp[0] 0所以公式给出2204这个 4 是错的。正确做法是回到定义以索引 4 结尾的子串是())根本没有任何合法括号子串以它为结尾所以dp[4] 0。问题出在哪出在“匹配成功”这个判定不够完整。虽然j 1位置的s[1]是(但s[1]和s[4]配对后中间夹的部分是s[2:4] ))这不是一个合法子串。而我的公式里的dp[i-1]应该代表“中间夹着的合法子串长度”。在这里dp[3] 2但它对应的子串是s[2:4] ()吗不是s[2:4]是))长度为 2却不是括号子串。问题就在这里——dp[3] 2这个状态本身是合法的对应()即s[2:4]但s[1]和s[4]之间夹住的部分是s[2:4]它的确是))不是dp[3]对应的那个子串。换句话说dp[i-1]所代表的合法子串必须恰好紧贴s[i-1]这个位置并且在j与i之间形成完整的覆盖否则不能直接套公式。这个反例说明dp[i] 的定义中“以 i 结尾”这一点必须严格执行。为了避免这类 bug我建议你用纸笔过一遍s()())这个用例把每一步的索引、j、dp值写出来。如果你能自己走通并发现dp[4]为什么是 0那边界问题基本就吃透了。3.3 完整代码与测试用例我把加好注释的代码贴出来再带上几个测试用例方便你直接跑验证。def longestValidParentheses(s: str) - int: n len(s) dp [0] * n ans 0 for i in range(1, n): if s[i] ): if s[i-1] (: # 并列结构...() if i 2: dp[i] dp[i-2] 2 else: dp[i] 2 else: # 嵌套结构...((...)) j i - dp[i-1] - 1 if j 0 and s[j] (: dp[i] dp[i-1] 2 if j 1: dp[i] dp[j-1] ans max(ans, dp[i]) return ans # 测试 print(longestValidParentheses((())) # 2 print(longestValidParentheses()()()))) # 4 print(longestValidParentheses(()(()))) # 6 print(longestValidParentheses()) # 0 print(longestValidParentheses(()) # 0 print(longestValidParentheses(()()())) # 6时间复杂度和空间复杂度都是 O(n)。空间上可以用滚动数组优化到 O(1) 吗这是很多面试官的追问点。答案是不行因为嵌套转移需要随机访问dp[j-1]j可能离i很远。你会看到后面讲的栈解法可以实现 O(n) 时间和 O(n) 空间的栈双指针解法能做到 O(1) 空间但动态规划解法在空间这块就是 O(n)。面试时需要如实说明。4. 栈解法与双指针解法什么时候该放弃 DP动态规划是这道题的“官方推荐”解法之一但学算法不能只抱着一种方案。栈解法和双指针解法各有独特的优势而且在工程实践中有些变种用栈更自然。我把三种方案全部拆开方便你按场景选择。4.1 栈解法用哨兵换整洁栈解法的核心理念是用栈存储字符的下标而不是字符本身。为什么要存下标因为只有下标才能算出长度。还是以s )()())为例逐步演示初始时在栈底压入一个-1作为“最后一个没有被匹配的右括号”的哨兵。遇到(把它的下标压入栈。遇到)弹出栈顶元素表示匹配了一个左括号。弹出后如果栈为空说明这个右括号是多出来的它不能和前面的任何左括号匹配把当前下标压入栈作为新的哨兵。如果栈不空当前)与栈顶元素之间的长度就是一个候选的最长有效子串长度用i - 栈顶下标更新答案。关键点就在第 3 步。哨兵的存在让代码不需要额外判断边界。举个例子s (()。下标 0 是(压栈。下标 1 是(压栈。下标 2 是)弹出栈顶的下标 1此时栈不空栈顶是 0长度 2 - 0 2答案是 2。到这里正确。但如果初始不压 -1在弹出 1 后栈就空了你会不知所措。有了 -1一切自然。再比如s )()下标 0 是)弹出栈顶的 -1栈空了把 0 压入。之后下标 2 是)弹出栈顶 1栈里剩 0长度 2 - 0 2答案 2。如果没有下标 0 这个新的哨兵计算长度时会错误地把 -1 当哨兵导致长度算错。栈解法的代码def longestValidParentheses_stack(s: str) - int: stack [-1] ans 0 for i, ch in enumerate(s): if ch (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: ans max(ans, i - stack[-1]) return ans这个解法的思维难度比动态规划低很多也更快写对。面试时如果时间紧张我建议优先写栈解法保底。4.2 双指针解法两个方向各扫一遍双指针解法的思路很巧妙。设置两个计数器left和right遍历字符串遇到(令left遇到)令right。当left right时说明当前扫过的区间是合法子串更新答案。当right left时说明这个)没有对应的(合法子串被打破重置两个计数器为 0。但只从左往右扫一遍会有问题。考虑s (()扫到索引 1 时left2, right0扫到索引 2 时left2, right1整个过程中left right从未成立答案就是 0但实际最长有效子串是()长度为 2在索引 1 和 2。问题出在哪里在于left一直大于right最后剩下的多余左括号无法被及时处理。解决办法是从右往左再扫一遍这次交换规则遇到)令right遇到(令left当left right时更新答案当left right时重置。双向扫描互补能把两种“多出来”的情况都覆盖。def longestValidParentheses_two_pointer(s: str) - int: ans 0 left right 0 n len(s) # 从左往右 for ch in s: if ch (: left 1 else: right 1 if left right: ans max(ans, left right) elif right left: left right 0 # 从右往左 left right 0 for ch in reversed(s): if ch ): right 1 else: left 1 if left right: ans max(ans, left right) elif left right: left right 0 return ans这个解法的时间复杂度 O(n)空间复杂度 O(1)是三种解法中最省内存的。代价是逻辑上不如 DP 直观论证用“双向扫描”换来完整性。4.3 三种方案对比与面试选型建议我把三种方案的优劣整理成一个表格方便你快速决策方案时间复杂度空间复杂度思维难度典型应用场景动态规划O(n)O(n)较高需要理解状态转移括号题变种很多时作为核心建模思路栈存下标O(n)O(n)较低好写好懂面试保底写法处理多种括号类型时优势明显双指针O(n)O(1)中等需要理解双向互补内存受限的竞赛环境或者需要极致空间时我的实际建议是面试第一遍写栈解法逻辑简单不容易出 bug然后如果面试官追问“能不能用动态规划”再把 DP 推一遍展示建模能力如果追问“能不能不用额外空间”再用双指针收尾。这三种方案本身就是一个很好的面试表演清单。5. 从这道题延伸出去的 DP 建模思维遇到新题怎么下手题目讲完了但真正值钱的往往是从一道题里抽出来的方法。我这些年刷题有一个体会动态规划题看起来千变万化但序列型 DP 的建模套路其实非常有限。这道“最长有效括号子串”恰好集中体现了序列型 DP 最核心的三个套路。5.1 套路一状态定义一定要选“以 i 结尾”而不是“前 i 个”这是整个序列型 DP 最核心的决策。背包问题喜欢用“前 i 个物品”但括号类、子串类问题一旦涉及“连续”“拼接”必须让状态跟“最后一个字符”绑定。反过来如果题目问的是“能否组成目标和”才倾向于用“前 i 个”。为什么“以 i 结尾”好用因为新增一个字符到末尾时它只可能跟紧邻的一小段产生关联——往前戳一个位置匹配或往前戳一个“合法子串”再匹配。这种“局部关联”可以用常数时间完成转移。如果你选了“前 i 个”新字符和之前所有状态都可能耦合转移方程往往无法写出来。5.2 套路二在括号类问题里右括号是“事件触发点”左括号是“状态重置点”你去看所有括号类 DP 的转移几乎都是在遇到)时才计算转移遇到(时直接把状态清零。这是由合法性本身决定的——任何有效的括号片段都以)结束。把右括号当作事件能帮你快速确定哪些位置需要状态更新。而栈解法里的哨兵思想本质也是“左括号进栈、右括号触发计算”。你在面对一个新的括号变种题时先问自己一句哪种字符能作为“事件触发点”然后围绕它设计状态。这能让你少走很多弯路。5.3 套路三复杂转移必须画图别在脑子里空想我说句实在话80% 的人不是不会写dp[i] dp[i-1] 2 dp[j-1]而是在某个具体输入上对不上号。我的习惯是推导新转移方程时在草稿纸上画一条横轴标上索引把j、i-1、i的位置圈出来再把dp[i-1]对应的子串用方括号框出来一眼就能看出需要加哪一段。这道题里最关键的是理解s[j]和s[i]配对后内部是dp[i-1]覆盖的区域外部前面是dp[j-1]覆盖的区域。两个区域紧贴才能让最后的结果最完整。我甚至建议你把代码简化成下面这样的“填空式”结构对每个i只关心三件事s[i]是什么、i-1是什么、j在哪里。每走一步都自问现在扫描到的位置合法子串的右端为什么是它、左端最远能延伸到哪。写清这三件事DP 题基本就通了。5.4 变种题练习从这道题能长出的几个分支掌握了这道题你可以顺手做下面几个变种检验自己是不是真懂了变种一不是求最长有效括号子串长度而是求有效括号子串的个数。这个其实更简单只需要统计每次匹配成功时的长度增量。变种二括号类型有三种()、[]、{}。此时动态规划不再适用因为你需要记录栈内未匹配的具体括号类型栈解法是唯一简洁的方案。这也是为什么我在前面表格里强调栈解法在“多种括号”场景的优势。变种三要求输出最长有效括号子串本身而不是长度。此时需要额外记录dp[i]达到最大值时的起始下标复杂度不变。变种四在括号子串的两侧加上字符限制比如“括号子串必须出现在指定位置之后”这种问题往往需要预处理一个前缀辅助数组再用 DP 结合二分查找。我在实际工程里碰到过一个很现实的变种文本编辑器里做括号匹配高亮不仅要判断当前光标所在位置的括号是否匹配还要高亮从匹配位置到当前位置的所有内容。这时候栈解法天然比 DP 好用因为你在扫描过程中就在维护未匹配的括号栈。这也印证了本章开头那句话解法选型要跟着场景走不要迷信某种结构。最后想分享一点我自己的体会。很长一段时间里我看到括号题就条件反射地用栈虽然能 AC但总感觉对问题理解不深。直到认认真真把 DP 解法推导了一遍我才意识到栈解法其实是对 DP 某种“贪心模拟”的等价实现。学会用多种视角看同一道题比多刷十道同类题的收获更大。推完dp[i]的状态转移你会发现动态规划并不是什么神秘的算法套路它就是用精确的状态定义和可推导的转移规则把一个看起来需要枚举的子空间压缩成一维表格把指数级搜索变成线性递推。这个过程本身比记住任何一道题的答案都更有价值。