C++で解く「友達ペアリング問題」｜動的計画法・再帰メモ化・空間最適化の3つの実装

C++ を使って「友達ペアリング問題（Friends Pairing Problem）」を解くプログラムを作成します。この問題では、グループ内の友人の人数を表す正整数 N が与えられます。

各友人には次の2つの選択肢があります。

• 誰ともペアを組まずに単独で残る
• グループ内の別の友人1人とペアを組む（各友人がペアを組めるのは一度だけ）

問題の例

具体例で問題を確認してみましょう。

入力: n = 3
出力: 4
説明:
グループの3人を A、B、C とすると、組み合わせ方は以下の4通りです。
{A}, {B}, {C}
{A, B}, {C}
{A, C}, {B}
{A}, {B, C}

解法のアプローチ

この問題を解く一つの方法は、n 人の友人に対して可能な組み合わせの総数を求める漸化式（一般式）を導くことです。グループに n 人の友人がいるとき、その組み合わせ方の総数を f(n) とします。

n 番目の友人に注目すると、取り得る行動は次の2パターンに分けられます。

• ケース1: n 番目の友人が単独で残る場合 ― グループの人数が1人減るため、残りの問題は f(N−1) になります。
• ケース2: n 番目の友人が他の誰かとペアを組む場合 ― ペアの相手は残り N−1 人の中から選べるため N−1 通りあり、それぞれについてさらに残り N−2 人の問題 f(N−2) が続きます。

以上より、次の漸化式が成り立ちます。

f(N) = f(N−1) + (N−1) × f(N−2)

初期条件は f(1) = 1、f(2) = 2 です。この式をもとに、複数の実装方法を紹介します。

実装1: 動的計画法（DPテーブル）

漸化式の結果を配列に小さい順に埋めていく、ボトムアップ方式の実装です。時間計算量・空間計算量はともに O(N) です。

#include <iostream>
using namespace std;

int countGroupPairing(int N){
    int dpArr[N + 1];
    for (int i = 0; i <= N; i++) {
        if (i <= 2)
            dpArr[i] = i;
        else
            dpArr[i] = dpArr[i - 1] + (i - 1) * dpArr[i - 2];
    }
    return dpArr[N];
}
int main(){
    int N = 6;
    cout<<"グループの人数: "<<N<<endl;
    cout<<"ペアの組み合わせの総数: "<<countGroupPairing(N);
    return 0;
}

出力

グループの人数: 6
ペアの組み合わせの総数: 76

実装2: 再帰＋メモ化（トップダウン）

漸化式をそのまま再帰で実装し、一度計算した値を配列に保存することで再計算を防ぐ方法です。ポイントは、メモ化配列の初期化（memset）を main 関数側で一度だけ行うことです。関数内で毎回初期化してしまうと、せっかく保存した計算結果が消えてしまいます。

#include <bits/stdc++.h>
using namespace std;
int dpArr[1000];

int countGroupPairing(int N){
    if (N <= 2)
        return dpArr[N] = N;
    if (dpArr[N] != -1)
        return dpArr[N];
    return dpArr[N] = countGroupPairing(N - 1) + (N - 1) * countGroupPairing(N - 2);
}
int main(){
    memset(dpArr, -1, sizeof(dpArr));
    int N = 6;
    cout<<"グループの人数: "<<N<<endl;
    cout<<"ペアの組み合わせの総数: "<<countGroupPairing(N);
    return 0;
}

出力

グループの人数: 6
ペアの組み合わせの総数: 76

実装3: 空間計算量 O(1) への最適化

もう一つの方法として、フィボナッチ数列の計算を最適化するのと同じ発想で、直前の2つの値だけを保持しながら反復計算を行う方法があります。これにより、空間計算量を O(1) まで削減できます。

#include <bits/stdc++.h>
using namespace std;

int countGroupPairing(int N){
    int val1 = 1, val2 = 2, val3 = 0;
    if (N <= 2) {
        return N;
    }
    for (int i = 3; i <= N; i++) {
        val3 = val2 + (i - 1) * val1;
        val1 = val2;
        val2 = val3;
    }
    return val3;
}
int main(){
    int N = 6;
    cout<<"グループの人数: "<<N<<endl;
    cout<<"ペアの組み合わせの総数: "<<countGroupPairing(N);
    return 0;
}

出力

グループの人数: 6
ペアの組み合わせの総数: 76

まとめ

N = 6 の場合、答えはいずれの方法でも 76 となります。3つの実装の特徴を整理すると、次のようになります。

• DPテーブル: 実装がシンプルで理解しやすい。時間 O(N) ／ 空間 O(N)
• 再帰＋メモ化: 漸化式をそのままコードに反映できる。時間 O(N) ／ 空間 O(N)
• 変数2つでの最適化: メモリ効率が最良。時間 O(N) ／ 空間 O(1)

なお、N が大きくなると答えは急激に増加するため、実際の実装ではオーバーフローに注意が必要です。必要に応じて long long 型や多倍長整数を使用することをおすすめします。