设元素入栈的顺序是1、2、3、…、n ，则所有可能的出栈序列共有几种，求详细解析啊！！！
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)!)
当然，对于计算机来说，直接用递推法也可以，递归需要注意子问题的重复求解，需要采用记忆法。否则时间复杂度会很大
画一个坐标，然后允许的走法是向上或者向右，（向上对应出栈，耐则向右对应入栈）这样就保证了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)!)
当然，对于计算机来说，直接用递推法也可以，递归需要注意子问题的重复求解，需要采用记忆法。否则时间复杂度会很大
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
|
广告 您可能关注的内容 |
