Q25 左右対称の二分探索木

PHPのソース

<?php

// 場合の数[部分木のノード数] の配列
$PatternCntArr = array();
$PatternCntArr[0] = 1;
$PatternCntArr[1] = 1;

for($I = 2 ; $I <= 19 ; $I++){
    $PatternCntArr[$I] = 0;

    //頂点の分を引いたノード数
    $NodeCnt = $I - 1;

    // 左部分木のノード数でループ
    for($J = 0 ; $J <= $NodeCnt ; $J++){
        $RightNodeCnt = $NodeCnt - $J;
        $PatternCntArr[$I] += $PatternCntArr[$J] * $PatternCntArr[$RightNodeCnt];
    }

    printf('ノード数%02dだと、%d通り' , $I , $PatternCntArr[$I]);
    echo PHP_EOL;
}

実行結果

ノード数02だと、2通り
ノード数03だと、5通り
ノード数04だと、14通り
ノード数05だと、42通り
ノード数06だと、132通り
ノード数07だと、429通り
ノード数08だと、1430通り
ノード数09だと、4862通り
ノード数10だと、16796通り
ノード数11だと、58786通り
ノード数12だと、208012通り
ノード数13だと、742900通り
ノード数14だと、2674440通り
ノード数15だと、9694845通り
ノード数16だと、35357670通り
ノード数17だと、129644790通り
ノード数18だと、477638700通り
ノード数19だと、1767263190通り

解説

動的計画法で解いてます。