笔试遇上这道题，算是倒霉了。当我看到 1 2 5 14 这样规律的时候，我就知道是调出卡特兰数的时候了。（切分三角网格的算法）

悲剧的是，我根本没记住公式。于是，查了维基百科。现再次记录于下：

这里面比较重要的是最后一个公式。（适用于循环解法）

我首先尝试的其实是第二个公式，很明显的递归，但缺点也很明显，因为这道题已然涉及到大数乘法运算，我这高配的机器跑n = 19的时候， 竟然也有了等待计算的时间。我改用循环，用最后一个公式，速度明显提升，n = 19毫无压力，20都没问题。

记公式的题，遇上就靠命了...