Pythonでn番目のカタラン数を計算するプログラム|再帰法と動的計画法

本記事では、n番目のカタラン数を計算する方法について解説します。

カタラン数(Catalan number)は、次の漸化式で定義される自然数の数列です。

$$C_{0}= 1,\quad C_{n+1}=\displaystyle\sum\limits_{i=0}^n C_{i}C_{n-i}\quad (n \geq 0)$$

n = 0, 1, 2, 3, … に対するカタラン数は、1, 1, 2, 5, 14, 42, 132, 429, … と続きます。

カタラン数は、再帰法と動的計画法のどちらのアプローチでも求めることができます。それでは、それぞれの実装方法を見ていきましょう。

方法1:再帰法

再帰を使うと、漸化式の定義をそのままコードに反映できます。ただし、同じ値を何度も再計算するため、nが大きくなると計算量が指数関数的に増大する点には注意が必要です。

コード例

# 再帰による解法
def catalan(n):
    # nが1以下の場合は1を返す
    if n <= 1:
        return 1
    # Catalan(n) = catalan(i) * catalan(n-i-1)
    res = 0
    for i in range(n):
        res += catalan(i) * catalan(n-i-1)
    return res

# メイン処理
for i in range(6):
    print(catalan(i))

実行結果

1
1
2
5
14
42

各変数と再帰呼び出しの流れは、下図のように展開されます。

方法2:動的計画法

動的計画法では、一度計算した値を表(配列)に保存して再利用します。そのため無駄な再計算が発生せず、計算量をO(n²)に抑えられます。

コード例

# 動的計画法による解法
def catalan(n):
    if (n == 0 or n == 1):
        return 1
    # 結果を格納するテーブルを作成
    catalan = [0 for i in range(n + 1)]
    # 初期値を設定
    catalan[0] = 1
    catalan[1] = 1
    # 漸化式に基づいて順に計算
    for i in range(2, n + 1):
        catalan[i] = 0
        for j in range(i):
            catalan[i] = catalan[i] + catalan[j] * catalan[i-j-1]
    return catalan[n]

# メイン処理
for i in range(6):
    print(catalan(i), end=" ")

実行結果

1 1 2 5 14 42

このように、テーブルに保存した値を再利用することで、再帰法と比べて大幅に高速にカタラン数を求められます。

まとめ

本記事では、n番目のカタラン数を生成する2つの方法――再帰法と動的計画法――について解説しました。小さなnであれば再帰法でも十分ですが、大きなnを扱う場合は動的計画法の方が効率的です。目的に応じて使い分けましょう。