题目定位
之所以适合 DP，是因为以 i 结尾的合法括号长度可以建立在前面已经算好的合法区间之上，只要能找到正确的匹配左括号。
关键观察
当 s[i] 为 ')' 时，它可能形成简单的 '()'，也可能接上更长的 '(前面合法段)' 模式。
目标复杂度
O(n) / O(n)
这题的解法思路怎么拆
1
之所以适合 DP，是因为以 i 结尾的合法括号长度可以建立在前面已经算好的合法区间之上，只要能找到正确的匹配左括号。
2
当 s[i] 为 ')' 时，它可能形成简单的 '()'，也可能接上更长的 '(前面合法段)' 模式。
3
先用自然语言命名状态。
4
列出哪些决策会转移到这个状态。
参考实现
Python# Generic pattern template
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
dp[i] = transition(dp, i)
# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = transition(dp, i, j)
常见坑点
warning
扩展前一段合法区间时，没有认真检查匹配左括号的位置。
warning
嵌套结构时忘了再加上 dp[j-1]。
高频追问
栈解法和 DP 解法怎么比较？
虽然多了索引判断，为什么整体还是 O(n)？
继续刷相关题
先把 动态规划 这个模式刷成体系，再去做更难变体。