【数据结构】n元素入栈求出栈组合数

题目 入栈n个数, 求出栈可能组合数有多少?


学过数据结构的肯定会记得根据入栈数量求出栈可能性组合数量有一个公式, 但有忘记了是什么公式, 是这个其实, 叫Catalan数:

C_{n}=\dfrac {1}{n+1}\begin{pmatrix} 2n \\ n \end{pmatrix}
也可以用递归公式:
f\left( n\right) =\sum ^{n-1}_{i=0}f\left( i\right) f\left( n-1-i\right)


具体可以看我手绘图:


image
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 1.把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不...
    曲终人散Li阅读 3,525评论 0 19
  • Swift1> Swift和OC的区别1.1> Swift没有地址/指针的概念1.2> 泛型1.3> 类型严谨 对...
    cosWriter阅读 11,737评论 1 32
  • 一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这...
    Winterfell_Z阅读 6,624评论 0 13
  • 记得小时候经常讲的一个故事:从前有座山,山上有座庙,庙里有一个老和尚和一个小和尚,一天,老和尚给小和尚讲了一个故事...
    IT可乐阅读 522评论 0 3
  • 一、Java基础 1. String类为什么是final的。 final修饰的类不能被继承,即它不能拥有自己的子类...
    vaneL阅读 963评论 0 3

友情链接更多精彩内容