“我经常有那种感觉，如果这个事情来了，你却没有勇敢地去解决掉，它一定会再来。生活真是这样，它会一次次地让你去做这个功课直到你学会为止。” —— 《像我这样笨拙地生活》
卡特兰数（Catalan number）是 组合数学 中一个常出现在各种 计数问题 中的 数列。
数列的前几项为：1,1, 2, 5, 14, 42, 132, 429, 1430, 4862，...
题目描述：
n 个元素进栈序列为：1，2，3，4，...，n，则有多少种出栈序列。
思路：
我们将进栈表示为 +1，出栈表示为 -1，则 1 3 2 的出栈序列可以表示为：+1 -1 +1 +1 -1 -1。
假设非法序列为 A，对应的序列为 B。每个 A 只有一个"第一个前缀和小于 0 的前缀"，所以每个 A 只能产生一个 B。而每个 B 想要还原到 A，就需要找到"第一个前缀和大于 0 的前缀"，显然 B 也只能产生一个 A。
#include <cstdio>
using namespace std;
long long catalan[1000005];
int main()
{
int n;
scanf("%d", &n);
catalan[0] = catalan[1] = 1;
for (int i = 2; i <= n; i++)
for (int j = 0; j <= i - 1; j++)
catalan[i] += catalan[j] * catalan[i - j - 1];
printf("%lld\n", catalan[n]);
return 0;
}
我有罪，从此与省二失之交臂。这一次就是在赛场上没认出来。关于括号的排列组合，在使劲想转移方程，卡了3h。