Java Program for Coin Change using the Space Optimized 1D array

Q: What is Java Program for Coin Change using the Space Optimized 1D array?

In this article, we will learn Java Program for Coin Change using the Space Optimized 1D array,This free Java tutorial for complete beginners will help you learn Java from scratch.

Q: How to use Java Program for Coin Change using the Space Optimized 1D array in Java?

The above recursive solution has Optimal Substructure and Overlapping Subproblems so Dynamic programming (Memoization) can be used to solve the problem. So 2D array can be used to store results of previously solved subproblems.

Java Program for Coin Change 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.

Step-by-step approach:

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:

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

Output

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

Please refer complete article on Coin Change | DP-7 for more details!

Java Program for Coin Change | DP-7

Write a Java program for a given integer array of coins[ ] of size N representing different types of denominations and an integer sum, the task is to find the number of ways to make a sum by using different denominations.

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}.