Count all combinations of coins to make a given value sum Dynamic Programming (Space Optimized)

Count all combinations of coins to make a given value sum using Dynamic Programming (Tabulation):

In the above tabulation approach we are only using dp[i-1][j] and dp[i][j] etc, so we can do space optimization by only using a 1d dp array.

Follow the below steps to Implement the idea:

Create a 1D dp array, dp[i] represents the number of ways to make the sum i using the given coin denominations.
The outer loop iterates over the coins, and the inner loop iterates over the target sums. For each dp[j], it calculates the number of ways to make change using the current coin denomination and the previous results stored in dp.
dp[sum] contains the total number of ways to make change for the given target sum using the available coin denominations. This approach optimizes space by using a 1D array instead of a 2D DP table.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
 
using namespace std;
 
// This code is 
int count(int coins[], int n, int sum)
{
    // table[i] will be storing the number of solutions for
    // value i. We need sum+1 rows as the dp is
    // constructed in bottom up manner using the base case
    // (sum = 0)
    int dp[sum + 1];
 
    // Initialize all table values as 0
    memset(dp, 0, sizeof(dp));
 
    // Base case (If given value is 0)
    dp[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 (int i = 0; i < n; i++)
        for (int j = coins[i]; j <= sum; j++)
            dp[j] += dp[j - coins[i]];
    return dp[sum];
}
 
// Driver Code
int main()
{
    int coins[] = { 1, 2, 3 };
    int n = sizeof(coins) / sizeof(coins[0]);
    int sum = 5;
    cout << count(coins, n, sum);
    return 0;
}

Java

/* Dynamic Programming Java implementation of Coin
Change problem */
import java.util.Arrays;
 
class CoinChange {
    static long count(int coins[], int n, int sum)
{
    // dp[i] will be storing the number of solutions for
    // value i. We need sum+1 rows as the dp is
    // constructed in bottom up manner using the base case
    // (sum = 0)
    int dp[] = new int[sum + 1];
 
    // Base case (If given value is 0)
    dp[0] = 1;
 
    // Pick all coins one by one and update the dp[]
    // values after the index greater than or equal to the
    // value of the picked coin
    for (int i = 0; i < n; i++)
        for (int j = coins[i]; j <= sum; j++)
            dp[j] += dp[j - coins[i]];
 
    return dp[sum];
}
 
    // Driver Function to test above function
    public static void main(String args[])
    {
        int coins[] = { 1, 2, 3 };
        int n = coins.length;
        int sum = 5;
        System.out.println(count(coins, n, sum));
    }
}
// This code is contributed by Pankaj Kumar

Python

# Dynamic Programming Python implementation of Coin
# Change problem
 
 
def count(coins, n, sum):
 
    # dp[i] will be storing the number of solutions for
    # value i. We need sum+1 rows as the dp is constructed
    # in bottom up manner using the base case (sum = 0)
    # Initialize all table values as 0
    dp = [0 for k in range(sum+1)]
 
    # Base case (If given value is 0)
    dp[0] = 1
 
    # Pick all coins one by one and update the dp[] values
    # after the index greater than or equal to the value of the
    # picked coin
    for i in range(0, n):
        for j in range(coins[i], sum+1):
            dp[j] += dp[j-coins[i]]
 
    return dp[sum]
 
 
# Driver program to test above function
coins = [1, 2, 3]
n = len(coins)
sum = 5
x = count(coins, n, sum)
print(x)
 
# This code is contributed by Afzal Ansari

C#

// Dynamic Programming C# implementation
// of Coin Change problem
using System;
 
class GFG {
    static int count(int[] coins, int n, int sum)
    {
        // dp[i] will be storing the
        // number of solutions for value i.
        // We need sum+1 rows as the dp
        // is constructed in bottom up manner
        // using the base case (sum = 0)
        int[] dp = new int[sum + 1];
 
        // Base case (If given value is 0)
        dp[0] = 1;
 
        // Pick all coins one by one and
        // update the dp[] values after
        // the index greater than or equal
        // to the value of the picked coin
        for (int i = 0; i < n; i++)
            for (int j = coins[i]; j <= sum; j++)
                dp[j] += dp[j - coins[i]];
 
        return dp[sum];
    }
 
    // Driver Code
    public static void Main()
    {
        int[] coins = { 1, 2, 3 };
        int n = coins.Length;
        int sum = 5;
        Console.Write(count(coins, n, sum));
    }
}
 
// This code is contributed by Raj

Javascript

<script>
    // Dynamic Programming Javascript implementation
    // of Coin Change problem
     
    function count(coins, n, sum)
    {
        // dp[i] will be storing the
        // number of solutions for value i.
        // We need n+1 rows as the dp
        // is constructed in bottom up manner
        // using the base case (sum = 0)
        let dp = new Array(sum + 1);
        dp.fill(0);
 
        // Base case (If given value is 0)
        dp[0] = 1;
 
        // Pick all coins one by one and
        // update the dp[] values after
        // the index greater than or equal
        // to the value of the picked coin
        for(let i = 0; i < n; i++)
            for(let j = coins[i]; j <= sum; j++)
                dp[j] += dp[j - coins[i]];
 
        return dp[sum];
    }
     
    let coins = [1, 2, 3];
    let n = coins.length;
    let sum = 4;
    document.write(count(coins, n, sum));
</script>

PHP

<?php
function count_1( &$coins, $n, $sum )
{
    // table[i] will be storing the number 
    // of solutions for value i. We need sum+1 
    // rows as the table is constructed in
    // bottom up manner using the base case (sum = 0)
    $table = array_fill(0, $sum + 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 < $n; $i++)
        for($j = $coins[$i]; $j <= $sum; $j++)
            $table[$j] += $table[$j - $coins[$i]];
 
    return $table[$sum];
}
 
// Driver Code
$coins = array(1, 2, 3);
$n = sizeof($coins);
$sum = 4;
$x = count_1($coins, $n, $sum);
echo $x;
 
// This code is contributed
// by ChitraNayal
?>

Output

Time complexity : O(N*sum)
Auxiliary Space : O(sum)

Count all combinations of coins to make a given value sum (Coin Change II)

Given an integer array of coins[ ] of size N representing different types of denominations and an integer sum, the task is to count all combinations of coins to make a given value sum.

Note: Assume that you have an infinite supply of each type of coin.

Examples:

Input: sum = 4, coins[] = {1,2,3},
Output: 4
Explanation: there are four solutions: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}.

Input: sum = 10, coins[] = {2, 5, 3, 6}
Output: 5
Explanation: There are five solutions:
{2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}.

Tags:

#Accolite #Microsoft #Morgan Stanley #Paytm #Samsung #Snapdeal #DSA #Dynamic Programming #Greedy #Mathematical #Accolite #Microsoft #Morgan Stanley #Paytm #Samsung #Snapdeal #Dynamic Programming #Greedy #Mathematical