Question

设元素入栈的顺序是1、2、3、…、n ，则所有可能的出栈序列共有几种，求详细解析啊！！！

我做了一天了，还是没有头绪，那位高手能够指点指点，感激不近啊！！！

Answer 1

这个递归公式很难推导，不过用计算机却很容易计算。做一个有效映射就可以了。
画一个坐标，然后允许的走法是向上或者向右，（向上对应出栈，向右对应入栈）这样就保证了y总是小于等于x，
然后(0,0)代表没有元素，有一种，（n,0)肯定也是一种，就是全部入栈，也就对应全部出栈。
对于任意一点(n,n),其走法应该是来自于(n,n-1) 没有左边过来的走法,对于其他的，总有左边过来的走法和下面过来的走法。

所以最终我得到的序列（从0个元素开始)是 1,1,2,5,14,42,132,429,...
这个就是卡特兰数，计算公式是C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!)
当然，对于计算机来说，直接用递推法也可以，递归需要注意子问题的重复求解，需要采用记忆法。否则时间复杂度会很大