# Make Change

```<?php

/**
* make_change
*
* Calculate the number of different ways there are to make change for a given amount.
*
* @version 0.1
* @author Contributors at eXorithm
* @link https://www.exorithm.com/algorithm/view/make_change Listing at eXorithm
* @link https://www.exorithm.com/algorithm/history/make_change History at eXorithm
*
* @param number \$amount How many cents you want to make change for.
* @param array \$coins The coin denominations you have.
* @return mixed
*/
function make_change(\$amount=100,\$coins=array(0=>'1',1=>'5',2=>'10',3=>'25'))
{
\$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];
}

?>
```