C++で二項係数を計算する方法：再帰と動的計画法による実装

二項係数とは

二項係数は C(n, k) または ⁿCᵣ と表記され、(1+X)ⁿ を二項展開したときの x^k の係数として定義されます。

また、二項係数は「n 個の要素の中から k 個を選ぶ方法の総数」、すなわち n 要素の集合から取り出す k 個の組み合わせ（k-combination）の数も表します。選ぶ順序は考慮されない点に注意してください。

この記事では、パラメータ n と k が与えられたときに、二項係数 ⁿCₖ の値を返すプログラムを C++ で実装します。

例

入力 : n = 8, k = 3
出力 : 56

この問題には複数の解法が存在します。以下では、代表的な2つのアプローチを紹介します。

解法1：再帰呼び出しによる一般的な解法

二項係数は、パスカルの三角形の性質に基づく次の漸化式を用いて再帰的に計算できます。

c(n, k) = c(n-1, k-1) + c(n-1, k)

c(n, 0) = c(n, n) = 1

この公式は「n 番目の要素を選ぶ場合と選ばない場合の数を足し合わせる」という考え方に基づいています。これを C++ で実装すると次のようになります。

実装例

#include <iostream>
using namespace std;
int binomialCoefficients(int n, int k) {
    if (k == 0 || k == n)
        return 1;
    return binomialCoefficients(n - 1, k - 1) + binomialCoefficients(n - 1, k);
}
int main() {
    int n = 8, k = 5;
    cout << "The value of C(" << n << ", " << k << ") is " << binomialCoefficients(n, k);
    return 0;
}

出力

The value of C(8, 5) is 56

この再帰的な解法はシンプルで直感的に理解しやすい反面、同じ部分問題が何度も計算されるため、計算量は指数オーダーで増大します。そのため、n や k が大きくなると実行時間が急激に伸びるという欠点があります。

解法2：動的計画法（DP）による効率的な解法

再帰解法では部分問題の重複（overlapping subproblems）が発生します。そこで、動的計画法を用いて計算済みの結果を配列に保存し、再計算を避けることで効率化できます。

以下の実装では、1 次元配列を使い、パスカルの三角形を 1 行ずつ右から更新していくことで、空間計算量を O(k) に抑えています。

実装例

#include <bits/stdc++.h>
using namespace std;
int binomialCoefficients(int n, int k) {
    int C[k + 1];
    memset(C, 0, sizeof(C));
    C[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = min(i, k); j > 0; j--)
            C[j] = C[j] + C[j - 1];
    }
    return C[k];
}
int main() {
    int n = 8, k = 5;
    cout << "The value of C(" << n << ", " << k << ") is " << binomialCoefficients(n, k);
    return 0;
}

出力

The value of C(8, 5) is 56

まとめ

二項係数の計算には、シンプルな再帰解法と動的計画法の 2 つのアプローチがあります。再帰解法はコードが短く理解しやすい一方で、計算量が指数オーダーになるため大きな入力には不向きです。一方、動的計画法を用いれば時間計算量 O(n×k)、空間計算量 O(k) で効率的に求められます。実用上は動的計画法による実装が推奨されます。