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 /algorithm/view/make_change Listing at eXorithm
 * @link /algorithm/history/make_change History at eXorithm
 * @license /home/show/license
 *
 * @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];
}

?>