[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 <= num; i++) {
    for (int j = 0; j < i; j++) {
        catalan[i] += (catalan[j] * catalan[i-j-1]);
    }
}

最后推荐这位大佬的题解 → Here
dalao讲述了递归/记忆化搜索、递推/ DP (动态规划)、数论做法_卡特兰/ Catalan、高精度/打表这样四种解法，感兴趣的自行学习，这种大神级别的题解本蒟蒻还写不出来，只能Orz并推荐给大噶。

AC代码（Java语言描述）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        scanner.close();
        int[] catalan = new int[num+1];
        catalan[0] = 1;
        catalan[1] = 1;
        for (int i = 2; i <= num; i++) {
            for (int j = 0; j < i; j++) {
                catalan[i] += (catalan[j] * catalan[i-j-1]);
            }
        }
        System.out.println(catalan[num]);
    }
}