加泰羅尼亞數演算法基本資訊

加泰羅尼亞數字演算法是動態規劃演算法。

在組合數學中，加泰羅尼亞數字形成一系列自然數，這些數字出現在各種計數問題中，通常涉及遞迴定義的物件。非負整數 n 上的加泰羅尼亞數是一組數字，這些數字出現在型別的樹列舉問題中，“如果不同的方向分別計算，有多少種方法可以將常規的 n-gon 分成 n-2 個三角形？”

加泰羅尼亞數字演算法的應用：

1. 在底行上堆疊硬幣的方式的數量，包括在平面中的 n 個連續硬幣，使得不允許硬幣放在底部硬幣的兩側，並且每個額外的硬幣必須高於另外兩個硬幣，第 n 個加泰羅尼亞號碼。
2. 將 n 對括號的字串分組的方式的數量，即每個左括號具有匹配的閉括號，是第 n 個加泰羅尼亞數。
3. 通過用直的非交叉線連線頂點將平面中的 n + 2 邊凸多邊形切割成三角形的方法的數量是第 n 個加泰羅尼亞數。這是 Euler 感興趣的應用程式。

使用從零開始的編號，通過以下等式直接根據二項式係數給出第 n 個加泰羅尼亞數。

加泰羅尼亞語數字示例：

這裡 n = 4 的值。（最好的例子 - 來自維基百科）

輔助空間： O(n)
時間複雜度： O(n^2)