PythonでN番目のカタラン数を計算する方法【再帰・動的計画法】

本記事では、N番目のカタラン数(Catalan number)を求める方法について解説します。

カタラン数とは、以下の漸化式で定義される自然数の数列です。

$$c_{0} = 1\;and\; c_{n+1} = \displaystyle\sum\limits_{i=0}^nc_{i} c_{n-i}\; for n\geq 0 ;$$

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

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

方法1:再帰による実装

# 再帰的な解法
def catalan(n):
    # n が 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

このコードでは、catalan() 関数が自分自身を呼び出しながら各項を順に計算します。n が 1 以下の場合は 1 を返し、それ以外の場合は catalan(i) × catalan(n-i-1) の総和を求めていきます。

再帰法はコードがシンプルで直感的に書ける一方、同じ値を何度も再計算してしまうため、n が大きくなると計算量が指数関数的に増加するという欠点があります。

方法2:動的計画法による実装

# 動的計画法を使用した解法
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

動的計画法では、一度計算した結果を配列(テーブル)に保存して再利用するため、無駄な計算が発生しません。その結果、計算量は O(n²) に抑えられ、再帰法と比べて大幅に効率が向上します。

まとめ

本記事では、Pythonを使ってN番目のカタラン数を生成する2つの方法――再帰法と動的計画法――について学びました。小さな n であれば再帰法でも十分ですが、パフォーマンスを重視する場合は、計算結果をキャッシュして再利用できる動的計画法の利用をおすすめします。