Q17 グループで乗るリフト

PHPのソース

<?php
Solve( 5,3);
Solve(32,6);

function Solve($pNinzuu , $pLiftMax)
{
    //場合の数[残り人数]なDP表
    $PrevDP = array($pNinzuu => 1);

    $Answer=0;
    while(true){
        $WillBreak = true;
        foreach (array_keys($PrevDP) as $EachKey){
            if($EachKey > 0) $WillBreak = false;
        }
        if($WillBreak) break;
        $CurrDP = array();

        foreach (array_keys($PrevDP) as $EachKey){
            for($I = 1 ; $I <= $pLiftMax ; $I++){
                $NewI = $EachKey - $I;
                if($NewI < 0) break;
                if(array_key_exists($NewI , $CurrDP))
                    $CurrDP[$NewI] += $PrevDP[$EachKey];
                else $CurrDP[$NewI] = $PrevDP[$EachKey];
            }
        }
        if(array_key_exists(0 , $CurrDP)) $Answer += $CurrDP[0];
        $PrevDP = $CurrDP;
    }
    echo "解は{$Answer}通り" . PHP_EOL;
}

実行結果

解は13通り
解は1721441096通り

解説

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