Unique Binary Search Trees

アルゴリズム概要

問題の説明

整数 n が与えられたとき、 1 から n までの連続整数をすべて使って構成できる「構造的に異なる二分探索木（BST）」の個数を返す問題です。

入出力例

Input: n = 3
Output: 5

Input: n = 1
Output: 1

制約条件

• 1 <= n <= 19

戦略

• 数学的背景: この問題は「n 番目のカタラン数 Cₙ」を求める問題に帰着される
• 漸化式の利用: C₀ = 1、Cₙ = Cₙ₋₁ × 2(2n - 1) / (n + 1) を利用
• ループ実装: 再帰やDP配列を使わず、O(1) 空間で計算
• 整数演算: Python の整数除算 // で誤差なく計算

主要ポイント

• 時間計算量: O(n) - ループが n 回実行
• 空間計算量: O(1) - 変数 c, i のみ使用
• 最適化手法: DP配列不要、再帰不要、定数空間で計算

ステップバイステップ解説

Python実装

class Solution:
    """
    Unique Binary Search Trees 問題を解くクラス。

    カタラン数の漸化式を用いてO(n)/O(1)で計算。
    """

    def numTrees(self, n: int) -> int:
        """
        LeetCode用エントリポイント（競技プログラミング向け実装）。

        Args:
            n: ノード数 (1 <= n <= 19)

        Returns:
            構造的に異なるBSTの個数

        Complexity:
            Time: O(n)
            Space: O(1)
        """
        # カタラン数の漸化式: C_0 = 1
        c: int = 1

        # C_n = C_{n-1} * 2(2n - 1) / (n + 1)
        for i in range(1, n + 1):
            # 整数除算で誤差なく計算
            c = c * 2 * (2 * i - 1) // (i + 1)

        return c

フローチャート

フローの説明：
1. 初期化: c = 1 で開始（C₀の値）
2. ループ開始: i = 1 から n まで反復
3. 条件分岐: i <= n であれば処理を続行、そうでなければ終了
4. 漸化式適用: c = c × 2(2i - 1) ÷ (i + 1) を計算
5. インクリメント: i を1増やす
6. ループバック: 条件分岐に戻る（紫の矢印）
7. 終了: ループ完了後、c を返す

計算量分析

他手法との比較