卡特兰数

XJack · 2019-10-04 17:23:02 · 个人记录

卡特兰数

基础公式

C_n=\displaystyle\sum_{i=0}^{n-1} C_0 * C_{n-1-i}

这个公式有很多的用处，在多次的提高组初赛中出现

那么具体是解决什么问题的呢？

典型例子

解决以下问题

• 给出需要压入栈的元素，求解此栈有多少种出栈方式

• 给出括号的对数，求解这么多组括号能组成多少组合法括号序列

• 给出节点个数，求能够组成多少个二叉树

• 给出多边形的个数，求将这个多边形剖成多个三角形的剖法的个数

此上的答案全部直接用C_n=\displaystyle\sum_{i=0}^{n-1} C_0 * C_{n-1-i}便可以推出

为什么

这里需要借助区间DP的一个重要的思想 找间隔点

对于上述的第一个问题，可以进行以下的分析：

将间隔点设置为某一个需要压入的数，当且仅当这个数之前的数都已经在他之前被弹出，且他之后被压入的数也在他之前被弹出。

经过这样分析对于每一个间隔点，都可以将整个的问题分为两个子问题 这个元素之前的所有元素当做一个独立的栈，这个元素之后的所有的元素当成一个独立的栈。

所以当这个点固定时整个栈一共有