algorithm
カタロニア数アルゴリズム

カタロニア数アルゴリズム基本情報

カタロニア数字アルゴリズムは動的プログラミングアルゴリズムです。

コンビナトリアル数学では、 カタロニア数は、さまざまなカウント問題で発生する自然数のシーケンスを形成し、しばしば再帰的に定義されたオブジェクトを含みます。非負整数nのカタロニア数は、 '異なる方向を別々に数えると、正則なn-gonをn-2個の三角形に何通りに分割できますか？'というツリー列挙問題で発生する数値の集合です。

カタロニア数アルゴリズムの応用：

1. コインが底部コインの2つの側面に置かれることができず、追加コインが2つの他のコインより上になければならないような、平面内のn個の連続するコインからなる最下行のコインを積み重ねる方法の数は、 n番目のカタロニア語の数字。
2. n個の括弧の列をグループ化する方法の数は、それぞれの開いた括弧が一致する閉じ括弧を持つように、n番目のカタロニア数です。
3. 頂点を直線で交差しない線で接続することによって平面内のn + 2面の凸多角形を三角形に切る方法の数は、n番目のカタロニア数です。オイラーが興味を持ったアプリケーションです。

ゼロベースの番号付けを使用すると、 n番目のカタラン数は、次の式によって二項係数によって直接与えられます。

カタロニア語の例：

ここではn = 4の値です（ベスト・プラクティス - Wikipediaより）

補助空間： O(n)
時間複雑度： O(n^2)

C＃の実装

public class CatalanNumber
{
    public static int Main(int number)
    {
        int result = 0;
        if (number <= 1) return 1;
        for (int i = 0; i < number; i++)
        {
            result += Main(i)*Main(number - i - 1);
        }
        return result;
    }
}