function make_change ($amount, $coins
{
$coin_count = count$coins);
$table = array();
for ($i = -1; $i <= $amount; $i++) {
for$j = -1; $j <= $coin_count; $j++) {
// Rules
// 1: table[0,0] or table[0,x] = 1
// 2: talbe[i <= -1, x] = 0
// 3: table[x, j <= -1] = 0
$total = 0;
// first sub-problem
// count(n, m-1)
$n = $i
$m = $j-1;
if ($n == 0) // rule 1
$total += 1;
else if ($n <= -1) // rule 2
$total += 0;
else if (($m <= 0) && ($n >= 1))
$total += 0;
else
$total += $table$n][$m];
// second sub-problem
// count(n-S[m], m)
if (($j-1) <= -1)
$total += 0;
else {
$n = $i - $coins$j - 1];
$m = $j
if ($n == 0) // rule 1
$total += 1;
else if ($n <= -1) // rule 2
$total += 0;
else if (($m <= 0) && ($n >= 1)) // rule 3
$total += 0;
else
$total += $table$n][$m];
}
$table$i][$j] = $total
}
}
return $table$i-1][$j-1];
}
eXorithm – Execute Algorithm: View / Run Algorithm make_change
