思路1，找递推（递归）关系式：定义：f(x, y)表示待入栈元素 x 个，栈内已有元素 y 个的情况下 可能输出序列的总数目。题目中求解的问题可表示为：f(n, 0)。 每个时刻栈的操作只有两个：入栈、出栈。 把这两种操作所对应的 可能输出序列总数量 加起来即得答案。 入栈：待入栈元素少一个，栈内元素加一个。 对应状态为：f(x-1, y+1)； 出栈：待入栈元素不变，栈内元素少一个。 对应状态为：f(x, y-1)； 则求解 f(x, y) 转化成了求解 f(x-1, y+1)+f(x, y-1)。 找到递推（递归）关系式，可用递推（二维递推），或者递归函数求解，递推注意边界条件的设置，递归注意递归出口的设置，对于本题，递归的方法因为牵涉到某些问题的反复求解，部分样例会超时。 递归实现代码 递推实现代码 思路2：卡特兰数-组合数学中一种重要的计数数列，用于描述“合法匹配”、“不越界”、“分治拆分”类问题的计数规律。本题涉及问题即为卡特兰数的一个典型应用场景。 卡特兰数：1、1、2、5、14、42、132... 原理： f(n+1)=∑i=0nf(i)∗f(n−i)f(n+1)=\sum_{i=0}^{n} f(i)*f(n-i)f(n+1)=∑i=0n f(i)∗f(n−i) (n>=0) 规模为 n+1 的问题，可以拆分成规模为 i 的问题和规模为 n-i 的两个子问题，累加所有情况。 卡特兰数的通项公式：f(n)=(2n)!(n+1)!⋅n!f(n)=\dfrac{(2n)!}{(n+1)!\cdot n!}f(n)=(n+1)!⋅n!(2n)! 本题n的值最大为18，如果直接使用卡特兰数的通项公式，会面临超出64位有符号整数存储范围的问题。因此要利用原理进行逐个推导。 f(n)=∑i=0n−1f(i)∗f(n−1−i)f(n)=\sum_{i=0}^{n-1} f(i)*f(n-1-i)f(n)=∑i=0n−1 f(i)∗f(n−1−i) (n>=0) 卡特兰数 感兴趣的同学可以再去查找一下卡特兰数的其他应用场景。