Java Program for Coin Change using Dynamic Programming (Tabulation)

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

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

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

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

Create a 2D dp array with rows and columns equal to the number of coin denominations and target sum.

dp[0][0] will be set to 1 which represents the base case where the target sum is 0, and there is only one way to make the change by not selecting any coin.

Iterate through the rows of the dp array (i from 1 to n), representing the current coin being considered.

The inner loop iterates over the target sums (j from 0 to sum).

Add the number of ways to make change without using the current coin, i.e., dp[i][j] += dp[i-1][j].

Add the number of ways to make change using the current coin, i.e., dp[i][j] += dp[i][j-coins[i-1]].

dp[n][sum] will contain the total number of ways to make change for the given target sum using the available coin denominations.

Below is the implementation of the above approach:

Java

import java.util.*;
 
public class CoinChangeWays {
    // Returns total distinct ways to make sum using n coins of
    // different denominations
    static int count(List<Integer> coins, int n, int sum) {
        // 2D dp array where n is the number of coin
        // denominations and sum is the target sum
        int[][] dp = new int[n + 1][sum + 1];
 
        // Represents the base case where the target sum is 0,
        // and there is only one way to make change: by not
        // selecting any coin
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= sum; j++) {
                // Add the number of ways to make change without
                // using the current coin
                dp[i][j] += dp[i - 1][j];
 
                if ((j - coins.get(i - 1)) >= 0) {
                    // Add the number of ways to make change
                    // using the current coin
                    dp[i][j] += dp[i][j - coins.get(i - 1)];
                }
            }
        }
        return dp[n][sum];
    }
 
    // Driver Code
    public static void main(String[] args) {
        List<Integer> coins = Arrays.asList(1, 2, 3);
        int n = 3;
        int sum = 5;
        System.out.println(count(coins, n, sum));
    }
}
// This code is contributed by Veerendra_Singh_Rajpoot

Output

Time complexity : O(N*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}.