Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn\’t matter.
For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.
Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.
Following is a simple recursive implementation of the Coin Change problem.
PHP
<?php// Recursive PHP program for// coin change problem.// Returns the count of ways we can // sum S[0...m-1] coins to get sum nfunction coun($S, $m, $n){ // If n is 0 then there is // 1 solution (do not include // any coin) if ($n == 0) return 1; // If n is less than 0 then no // solution exists if ($n < 0) return 0; // If there are no coins and n // is greater than 0, then no // solution exist if ($m <= 0 && $n >= 1) return 0; // count is sum of solutions (i) // including S[m-1] (ii) excluding S[m-1] return coun($S, $m - 1,$n ) + coun($S, $m, $n - $S[$m - 1] );} // Driver Code $arr = array(1, 2, 3); $m = count($arr); echo coun($arr, $m, 4); // This code is contributed by Sam007?> |
PHP
<?php// PHP program for // coin change problem.function count1($S, $m, $n){ // We need n+1 rows as // the table is constructed // in bottom up manner // using the base case 0 // value case (n = 0) $table; for ($i = 0; $i < $n + 1; $i++) for ($j = 0; $j < $m; $j++) $table[$i][$j] = 0; // Fill the entries for // 0 value case (n = 0) for ($i = 0; $i < $m; $i++) $table[0][$i] = 1; // Fill rest of the table // entries in bottom up manner for ($i = 1; $i < $n + 1; $i++) { for ($j = 0; $j < $m; $j++) { // Count of solutions // including S[j] $x = ($i-$S[$j] >= 0) ? $table[$i - $S[$j]][$j] : 0; // Count of solutions // excluding S[j] $y = ($j >= 1) ? $table[$i][$j - 1] : 0; // total count $table[$i][$j] = $x + $y; } } return $table[$n][$m-1];}// Driver Code$arr = array(1, 2, 3);$m = count($arr);$n = 4;echo count1($arr, $m, $n);// This code is contributed by mits?> |
Following is a simplified version of method 2. The auxiliary space required here is O(n) only.
PHP
<?phpfunction count_1( &$S, $m, $n ){ // table[i] will be storing the number // of solutions for value i. We need n+1 // rows as the table is constructed in // bottom up manner using the base case (n = 0) $table = array_fill(0, $n + 1, NULl); // Base case (If given value is 0) $table[0] = 1; // Pick all coins one by one and update // the table[] values after the index // greater than or equal to the value // of the picked coin for($i = 0; $i < $m; $i++) for($j = $S[$i]; $j <= $n; $j++) $table[$j] += $table[$j - $S[$i]]; return $table[$n];}// Driver Code$arr = array(1, 2, 3);$m = sizeof($arr);$n = 4;$x = count_1($arr, $m, $n);echo $x;// This code is contributed// by ChitraNayal?> |
Please refer complete article on Coin Change | DP-7 for more details!
<!–
–>
Report Issue
<!–
Please write us at contribute@geeksforgeeks.org to report any issue with the above content
–>
Please Login to comment…