PHP Program for Coin Change | DP-7

0 0 3 minutes read

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 n
function 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

<?php
function 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
?>