Java Program for Coin Change using Dynamic Programming (Memoization)

Q: What is Java Program for Coin Change using Dynamic Programming (Memoization)?

In this article, we will learn Java Program for Coin Change using Dynamic Programming (Memoization),This free Java tutorial for complete beginners will help you learn Java from scratch.

Java Program for Coin Change using Recursion:

Java Program for Coin Change using Dynamic Programming (Tabulation):

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.

Step-by-step approach:

Create a 2D dp array to store the results of previously solved subproblems.
dp[i][j] will represent the number of distinct ways to make the sum j by using the first i coins.
During the recursion call, if the same state is called more than once, then we can directly return the answer stored for that state instead of calculating again.

Below is the implementation of the above approach:

Java

// Java program for the above approach
import java.util.*;
 
class GFG {
    // Recursive function to count the numeber of distinct
    // ways to make the sum by using n coins
    static int count(int[] coins, int sum, int n,
                    int[][] dp)
    {
    // Base Case
        if (sum == 0)
            return dp[n][sum] = 1;
     
    // If number of coins is 0 or sum is less than 0 then
        // there is no way to make the sum.
        if (n == 0 || sum<0)
            return 0;
 
        // If the subproblem is previously calculated then
        // simply return the result
        if (dp[n][sum] != -1)
            return dp[n][sum];
 
    // Two options for the current coin
        return dp[n][sum]
            = count(coins, sum - coins[n - 1], n, dp)
            + count(coins, sum, n - 1, dp);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int tc = 1;
        while (tc != 0) {
            int n, sum;
            n = 3;
            sum = 5;
            int[] coins = { 1, 2, 3 };
            int[][] dp = new int[n + 1][sum + 1];
            for (int[] row : dp)
                Arrays.fill(row, -1);
            int res = count(coins, sum, n, dp);
            System.out.println(res);
            tc--;
        }
    }
}

Output

Time Complexity: O(N*sum), where N is the number of coins and sum is the target sum.
Auxiliary Space: O(N*sum)

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