例題 人数の分け方のパターン

PHPのソース

<?php
function Solve($pN){
    $UB = $pN;

    // 場合の数[配置済の人数]
    $DP = array();
    for( $I = 0 ; $I <= $UB ; $I++){
        $DP[$I] = 0;
    }
    $DP[0] = 1;

    for( $I = 2 ; $I <= 10 ; $I++){
        for( $J = 0 ; $J <= $UB ; $J++){
            if ($DP[$J] == 0) continue;

            $NewJ = $J + $I;
            if ($NewJ > $UB) break;

            $DP[$NewJ] += $DP[$J];
        }
    }
    printf('人数合計が%dだと、%d通り', $pN , $DP[$UB]);
    echo PHP_EOL;
}

Solve(  6); //     4
Solve(100); //437420

実行結果

人数合計が6だと、4通り
人数合計が100だと、437420通り

解説

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