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

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

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

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

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

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

StackOverflow 文档

加泰罗尼亚语数字示例:

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

StackOverflow 文档

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