题目
分析
直觉告诉我们，这里涉及到递推（递归）。
首先，如果有0个或者1个元素，只有1种出栈方式。这是初始条件。
如果有n个元素，考虑第i个元素的出栈方式：
- 前面进栈的
i-1个元素，有f(i-1)种出栈方式，后面进栈的n-i元素，有f(n-i)种出栈方式。 - 这两批元素的出栈方式是独立的，所以适用乘法原理：\(f(i-1)\times f(n-i)\)。
进行一些研究，就会发现这个递推公式实际上在计算所谓的卡塔兰数。除了本题的应用外，还有很多实际应用。
答案
思考
这道题就是想清楚两点：
- 递推的出发点：以第
i个元素作为分割，将整个入栈的元素分为两部分（不包括自己）。 - 左右部分的出栈方式可以递推（递归）解决。然后用乘法原理。当然，对所有的方式计数，是要累加的。