加泰罗尼亚数算法基本信息

加泰罗尼亚数字算法是动态规划算法。

在组合数学中，加泰罗尼亚数字形成一系列自然数，这些数字出现在各种计数问题中，通常涉及递归定义的对象。非负整数 n 上的加泰罗尼亚数是一组数字，这些数字出现在类型的树枚举问题中，“如果不同的方向分别计算，有多少种方法可以将常规的 n-gon 分成 n-2 个三角形？”

加泰罗尼亚数字算法的应用：

1. 在底行上堆叠硬币的方式的数量，包括在平面中的 n 个连续硬币，使得不允许硬币放在底部硬币的两侧，并且每个额外的硬币必须高于另外两个硬币，第 n 个加泰罗尼亚号码。
2. 将 n 对括号的字符串分组的方式的数量，即每个左括号具有匹配的闭括号，是第 n 个加泰罗尼亚数。
3. 通过用直的非交叉线连接顶点将平面中的 n + 2 边凸多边形切割成三角形的方法的数量是第 n 个加泰罗尼亚数。这是 Euler 感兴趣的应用程序。

使用从零开始的编号，通过以下等式直接根据二项式系数给出第 n 个加泰罗尼亚数。

加泰罗尼亚语数字示例：

这里 n = 4 的值。（最好的例子 - 来自维基百科）

辅助空间： O(n)
时间复杂度： O(n^2)