还爆栈了
by libra9z @ 2019-11-16 13:36:39
~~像我只能做$O(n^2)$~~
by FlaaST @ 2019-11-16 13:37:04
@[libra9z](/user/114495) 最好跑到$O（n lg n)$（完全二叉树）
by FlaaST @ 2019-11-16 13:37:59
不是用深搜吗，一遍dfs然后维护栈
by fzwfzwfzw @ 2019-11-16 13:38:09
dfs
dfs的时候带一个stack下去
by Cchen77 @ 2019-11-16 13:38:25
dfs一遍，做法和链差不多
by 彼岸归航 @ 2019-11-16 13:39:11
O(N)
by AK_Automata @ 2019-11-16 13:39:13
@[Cchen77](/user/169640) +1
by AK_Automata @ 2019-11-16 13:39:18
但是就我在考场上最大的样例RE了？
by AK_Automata @ 2019-11-16 13:39:34
考虑$ans[i]$表示以$i$结尾的合法串个数， 然后记录$pre[i]$表示在$i$之前的最后一个没有被匹配的左括号
然后直接就$O(n)$dp掉了
by Rainy_chen @ 2019-11-16 13:39:46