C++で解く「交差しない握手」問題 ― 動的計画法による数え方

円形に並んだ偶数 n 人の人々が、それぞれ別の誰かと握手をします。このとき、握手は全部で n / 2 回行われることになります。ここで求めたいのは、どの握手同士も互いに交差しないような握手の組み合わせが何通りあるかという数です。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返します。

例えば、入力が n = 2 の場合、出力は 1 になります。

解法のアプローチ

この問題は、有名なカタラン数（Catalan number）と同じ構造を持っています。動的計画法（DP）を使うことで効率的に解くことができます。

考え方のポイントは次の通りです。ある1人の人が誰かと握手すると、その握手によって円は2つの独立したグループに分割されます。分割された各グループの中でも、同じ条件（交差しない握手）で再帰的に数えられるため、次のような漸化式が成り立ちます。

• m := 10^9 + 7
• サイズ (n + 1) の配列 dp を定義する
• dp[0] := 1（人がいない場合は1通りとする）
• i を 0 から n まで 2 ずつ増やしながら、以下を繰り返す：
  • j を 0 から i - 2 まで 2 ずつ増やしながら、以下を繰り返す：
    • dp[i] := dp[i] + (dp[j] mod m × dp[i - 2 - j] mod m)
    • dp[i] := dp[i] mod m
• dp[n] mod m を返す

この漸化式では、i 人のうち最初の人が j 番目の位置の人と握手すると、残りの i - 2 - j 人がもう一方の側に分かれるため、dp[j] × dp[i - 2 - j] 通りの組み合わせが生まれます。

実装例

理解を深めるために、以下の C++ 実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9+7;
typedef long long int lli;
class Solution {
    public:
    int numberOfWays(int n) {
        vector <lli> dp(n+1);
        dp[0] = 1;
        for(int i = 0; i <= n; i+=2 ){
            for(int j =0 ; j <= i-2; j+=2){
                dp[i] += (dp[j]%m * dp[i-2-j]%m)%m;
                dp[i]%=m;
            }
        }
        return dp[n]%m;
    }
};
main(){
    Solution ob;
    cout << (ob.numberOfWays(2));
}

入力

2

出力

1

まとめ

このアルゴリズムの計算量は、外側のループと内側のループがそれぞれ O(n) 回ずつ回るため、全体で O(n²) となります。空間計算量は DP 配列の分だけの O(n) です。カタラン数の性質を利用することで、交差しない握手の組み合わせを効率よく求められるのがポイントです。