Q19 バランスのよいカーテンフック

PHPのソース

<?php
Solve( 6,4);
Solve(50,35);

function Solve($pRunner,$pHook)
{
    $UB = $pRunner - 3;

    //場合の数[現在位置]なDP表
    $PrevDP = array();
    $PrevDP[0] = 1;

    for($I = 1; $I <= $pHook - 2 ; $I++){
        $CurrDP = array();

        foreach($PrevDP as $EachKey => $EachVal){
            if($UB < $EachKey) continue;
            for($J = 0 ; $J <= 1 ; $J++){
                $NewKey = $EachKey + $J + 1;

                if(array_key_exists($NewKey,$CurrDP))
                    $CurrDP[$NewKey] += $PrevDP[$EachKey];
                else $CurrDP[$NewKey] = $PrevDP[$EachKey];
            }
        }
        //echo "{$I}回目のDP結果";
        //var_export($CurrDP);
        $PrevDP = $CurrDP;
    }
    $Answer = 0;
    for($I = 0 ; $I <= 1 ; $I++){
        if($PrevDP[$UB + $I] > 0)
            $Answer += $PrevDP[$UB + $I];
    }
    printf('ランナー数=%d,フック数=%dだと、%d通り',$pRunner,$pHook,$Answer);
    echo PHP_EOL;
}

実行結果

ランナー数=6,フック数=4だと、3通り
ランナー数=50,フック数=35だと、1855967520通り

解説

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