「もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら」を解いてみた その2

「もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら」を解いてみた
の続きです

動的計画法のコードをPHPで書いてみました
（Rubyのコードとロジックは同じです）

<?php
$M = trim(fgets(STDIN)); // 人員
$N = trim(fgets(STDIN)); // 会社数

$minCost = 0;
$num = array();
$cost = array();

for($i = 0; $i < $N; $i++) {
    fscanf(STDIN, '%d %d', $num[$i], $cost[$i]);
    $minCost += $cost[$i];
}

$dp[0] = 0;
for($n = 0; $n < $N; $n++) {
    foreach ($dp as $key => $value) {
        $totalNum = $key + $num[$n];
        $totalCost = $value + $cost[$n];
        if (isset($dp[$totalNum]) == false) {
            $dp[$totalNum] = $totalCost;
        } else {
            if ($dp[$totalNum] > $totalCost) {
                $dp[$totalNum] = $totalCost;
            }
        }
        if ($totalNum >= $M && $minCost > $totalCost) {
            $minCost = $totalCost;
        }
    }
}

//ksort($dp);
//var_dump($dp);
echo $minCost;

人数ごとの結果を残して、再利用しています（わかりにくい..）
一番低いコストの値だけを残しています
まだ無駄のあるコードで、改良の余地ありです

paizaでコードを提出すると採点してくれます
結果はこんな感じです
http://paiza.jp/poh/kirishima/result/fb88794dc2e25c011a242f318744ccc9

最速コードを目指したりするとまだ遊べるようです