因为这篇题解原文是用 Markdown 写成，在 我的博客 上面可能会有更好的阅读体验

考虑一个合法的括号序列长什么样子：(...) ，即由外面的括号和里面的部分组成，有用的信息来自于内部，于是我们关注内部可以由什么组成：

根据定义，一个合法的括号序列，内部可以是：S、AA、ASA、A、AS、SA，其中，AA 和 ASA 比较特殊，因为它们本身就是一个 A，信息被包含在 A 中。于是得到一个公式：

$$A_{i, j} = A_{i + 1, j - 1} + S_{i + 1, j - 1} + AS_{i + 1, j - 1} + SA_{i + 1, j - 1} \notag$$

接下来，我们考虑这些部分的信息如何维护：

1. 对于 A：我们若将这个递推公式深究到底，会得到什么？什么情况下就递归不下去了？也许最后的 A 是一个 ()，这当然合法，并且这个信息无法从别处递推来，于是，对于这个，我们在遇到的时候需要统计一下。或者，(S) 也是一个合法的括号序列，再往下深究，就是一个 S ，就是说，如果 (S) 放到上面的公式中，最后会得到一个 S 的值，显然这个值得是 $1$
2. 对于 S：经过上面的讨论，$\forall i, j \in \mathbb{N^+}, S_{i, j} = 1$ 而这个等式成立的前提是 $i, j$ 中间的部分完全由 '*' 组成

对于 AS，SA，ASA，AA 这些由 A 和 S 这两个比较基本的部分组成的部分，我们用乘法原理，可以求出它们的值。即：

$$AS_{i, j} = \sum_{i \le k \le j}A_{i, k} \times S_{k + 1, j} \notag \\ SA_{i, j} = \sum_{i \le k \le j}S_{i, k} \times A_{k + 1, j} \notag \\ ASA_{i, j} = \sum_{i \le k \le j}A_{i, k} \times SA_{k + 1, j} \notag \\ AA_{i, j} = \sum_{i \le k \le j}A_{i, k} \times A_{k + 1, j} \notag \\$$

需要注意的是，如果我们将 AA 和 ASA 的信息累加到 A 中，会导致原来的信息被覆盖掉，导致出错，所以在程序实现中我们需要用一个数组来备份合并操作之前的信息。