Q26 回数指定のじゃんけん

PHPのソース

<?php error_reporting(E_ALL);

const ACoin = 10;
define('TotalCoin' , ACoin + 10);
const Jyougen = 24;

//場合の数[Aのコイン枚数]なDP表
$PrevDP = array(ACoin => 1);

$Answer = 0;
for($I = 1 ; $I <= Jyougen ; $I++){
    $CurrDP = array();
    foreach($PrevDP as $EachKey => $EachVal){
        for($J = -1 ; $J <= 1 ; $J++){
            $NewKey = $EachKey + $J;
            if(array_key_exists($NewKey,$CurrDP))
                $CurrDP[$NewKey] += $EachVal;
            else $CurrDP[$NewKey] = $EachVal;
        }

        //解を計上
        if(array_key_exists(TotalCoin,$CurrDP)){
            $Answer += $CurrDP[TotalCoin];
            unset($CurrDP[TotalCoin]);
        }
        if(array_key_exists(0,$CurrDP)){
            $Answer += $CurrDP[0];
            unset($CurrDP[0]);
        }
    }
    $PrevDP = $CurrDP;
}
echo "解は{$Answer}通り";

実行結果

解は1469180016通り

解説

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