トップページに戻る
次のPHPのサンプルへ
前のPHPのサンプルへ
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通り
解説
動的計画法で解いてます。