题目内容

有一个叫塔子哥的程序员，他正在为他的新项目编写代码。这个项目需要验证一个字符串是否为合法的括号序列。

题目思路

经典的合法括号统计模型。观察到题目数据只有$2000$ , 那么考虑动态规划:

$dp_{i,j}$ 代表填完前i个数，并且左括号比右括号多$j$个的方案数。最后的答案是$dp_{n,0}$

为什么要这么定义:一个合法括号序列，他的充分必要条件是:每个前缀的左括号个数都不少于右括号个数，且整体的左括号个数 = 右括号个数

转移就很简单了: