出栈顺序(卡特兰数)


题目描述:

按照1,2,...,n-1,n的顺序入栈,问可以得到多少种出栈序列。如n=3时有1 2 3,1 3 2,2 1 3,2 3 1,3 2 1共5种出栈序列。

解题思路:

设f(n)为n个数时的方案数。

可知 f(0)=1; f(1)=1; f(2)=2; f(3)=5;

当n=4时 :

F1 F2 F3 F4

1  2  3  4 //四种状态分别标记为F1,F2,F3,F4

若F1 位于一号位置 则之前的数字出栈顺序的情况数为F(0),在一号位置后的数字出栈顺序的情况数为f(3);

则F1 位于一号位置时方案总数为f(0)*f(3);

若F1 位于二号位置 则F1之前的位置的数字出栈顺序的情况数可知为f(1),在二号位置之后的数字的出栈顺序为f(2)。

则F1位于二号位置时方案总数为f(1)*f(2);

同理:F1位于三号位置时 方案数为 f(2)*f(1);

   F1位于四号位置时 方案数为f(3)*f(0);

由上述条件可以推出:

  f(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0);

则当n未知时由以上结论可推:

  f(n)=f(0)*f(n-1)+f(1)*f(n-2)+f(2)*f(n-3)......f(n-2)*f(1)+f(n-1)*f(0);

以上就是本题的一般递推式,我们会发现 这个式子的实际时间复杂度为O(n^2);

当然不是很快,于是我们引入 卡特兰数;

所谓卡特兰数 就是 当递推式中出现 h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2) 时,

可知代数式的解为        h(n)=C(2n,n)/(n+1) (n=0,1,2,...);

它的另类递推式为        h(n)=h(n-1)*(4*n-2)/(n+1);    //本人数学弱渣 具体怎么推导请找百度君

于是乎我们的式子就化简为了 f(n)=f(n-1)*(4*n-2)/(n+1);// 优先级一定不要搞错 优先级害我找了好久bug

优质内容筛选与推荐>>
1、Multi chip package多芯片封装技术对比
2、linux 下安装及查看java的安装路径
3、虚拟机类加载机制
4、Docker.[1].环境准备.
5、[2019HDU多校第一场][HDU 6578][A. Blank]


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号