[Catalan]求解随机出栈可能数（洛谷P1044题题解，Java语言描述）

题目要求

P1044题目链接

分析

题意就是：N个数依次进栈，可随机出栈，算一下可能的出栈序列数。

其实这个就是Catalan啊，如果数据结构与算法有一定的刷题积累的学生应该经常做这样的About栈的题：

• 下列出栈序列中可能的是()
• 下列出栈序列中不可能的是()
• 出栈的可能序列数是多少？

前两种你可以自己推一推，最后一种总不能乱猜吧？ 而结论正是来源于此呢。

我比较菜，就学了大佬的Catalan解法做的题并简单写写题解。

建立int类型数组catalan。 catalan[i]表示i个数出栈的全部可能数。 先初始化两个值：catalan[0] = 1, catalan[1] = 1。 这是显然的，不解释。

设x为当前出栈序列的最后一个，则x有n种取值。

而由于x是最后一个出栈的，所以可以将已经出栈的数分成两部分：

• 比x小
• 比x大

比x小的数有x-1个，所以这些数的全部出栈可能为catalan[x-1]; 比x大的数有N-x个，所以这些数的全部出栈可能为catalan[n-x]。

这两部分互相影响，所以一个x的取值能够得到的所有可能性为catalan[x-1] * catalan[n-x]

另外，由于x有n个取值，所以得到最终的式子：

catalan[n] = f[0] * f[n-1] + f[1] * f[n-2] + … + f[n-1] * f[0]

下面是核心算法的Java实现代码：

catalan[0] = 1;
catalan[1] = 1;
for (int i = 2; i