题意 题目链接 给出一个长度为 $m$ 的括号串，在其前后增添字符构造长度为 $n$ 的合法括号串，求方案数。满足 $n-m \le 2000$。 解析 容易发现这是一道 dp 且复杂度基于 $n-m$。 我们已知中间的那条括号串 $S$，需要构造出左边的 $P$ 和右边的 $Q$（当然也可能为空）。通过 dp 方程转移时，考虑需要满足的两个条件，…