C++で解くユニークな二分探索木の数え上げ問題

問題の概要

整数 n が与えられたとき、値 1 から n までを格納する構造的に異なる二分探索木（BST）が何通り存在するかを求める問題です。

例えば、入力が 3 の場合、答えは 5 となります。考えられる木の構造は以下の通りです。

アプローチ：動的計画法（DP）

この問題は動的計画法を使うことで効率的に解けます。ポイントは、「i 個のノードからなる二分探索木の総数」を「より小さい部分問題の答え」から組み立てられることにあります。

根の値を j と固定すると、左部分木には 1〜j-1 の j-1 個の値が入り、右部分木には j+1〜i の i-j 個の値が入ります。したがって、次の漸化式が成り立ちます。

dp[i] = Σ (dp[j] × dp[i-1-j])　（j = 0 〜 i-1）

ここで dp[j] は「j 個のノードで作れるBSTの数」、dp[i-1-j] は「残りのノードで作れる右部分木の数」を表します。

アルゴリズムの手順

• サイズ n+1 の配列 dp を用意する
• dp[0] := 1（空の木は1通りとみなす）
• i を 1 から n まで繰り返す
  • j を 0 から i-1 まで繰り返し、dp[i] += dp[i-1-j] × dp[j] を計算する
• 最後に dp[n] を返す

C++による実装例

以下のコードで実際の実装を確認できます。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int numTrees(int n) {
        vector <int> dp(n+1);
        dp[0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < i; j++){
                dp[i] += (dp[i-1-j] * dp[j]);
            }
        }
        return dp[n];
    }
};
main(){
    Solution ob;
    cout << ob.numTrees(4);
}

入力例

4

出力例

14

補足：カタラン数との関係

この問題の答えは実はカタラン数（Catalan number）と一致することが知られています。つまり、答えは C(n) = (2n)! / ((n+1)! × n!) という閉形式でも求められます。ただし、DPによる解法は O(n²) の時間計算量・O(n) の空間計算量で直感的に理解しやすいため、面接などではこちらのアプローチが好まれることが多いです。