Java Program for Coin Change using the Space Optimized 1D array
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 sumi
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 indp
. 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 |
5
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}.
Contact Us