卡特兰数

· · 个人记录

一个树，度数 \leq 2时，他是二叉树

所以，我们有以下任务。

一个节点能构成 1 个二叉树

二个节点两个。

所以四个呢？

我们用递归：

只有左子树 5 个，有左有右占 4 个，右子树 5 个。

所以:

左0右4，左1右3....

f(5)=f(0) \times f(4)+ f(1) \times f(3) \cdots + f(4) \times f(0) f(n)=f(0) \times f(n-1) + f(1) \times f(n-2) \cdots + f(n-1) \times f(0)

所以卡特兰数乃此道理。

1，1，2，3，5，14

用到类型：括号匹配，分割图像