Coin change problem in dynamic programming
In this tutorial, we will understand a popular problem called the coin changeproblem through dynamic programming. This problem checks the logical and critical thinking ability of the person. Dynamic Programming is a popular algorithm method to solve optimization problems by breaking them into easier subproblems.
We will generate java programs to understand our topic practically.
Introduction to Coin Change Problem
Problem statement
An array of coins with differing values and an integer sum is provided.
It is asked to generate a combination of minimum possible coins to reach the given integer sum. If in case that sum cannot be reached, just return -1.
Now, let us try to understand the coin change problem through examples.
Example 1:
Array 1: {5, 7, 9, 12, 15, 35, 45};
There are 7 array elements present inside the above array. These array elements serve as the value of coins. The coin change problem aims to collect a certain amount of money using the minimum possible number of coins.
It is to be noted that the given values are associated with an infinite number of coins. In other words, you are allowed to use these values any number of times you require.
Example 2:
Array 2: {1, 2, 4, 6, 7, 12, 15, 16};
Required Sum: 8
The coins needed to reach the goal amount i.e 8: {2, 6}
Thus, to reach the goal amount, only two coins are required in the dynamic programming technique.
Now, let us see it for the greedy algorithm.
The coins needed to reach the goal amount i.e 8: {2, 2, 4}
In this case, the required number of coins is three. This is because the latter does local optimization.
Example 3:
Array 3: {2, 6, 10, 12, 14, 16};
Required Sum: 17
Output: -1
There are no possible combinations to get the sum as 17. Thus, the output is 17.
Solutions to the Coin Change Problem
Two solutions to the Coin Change Problem exist–
- Recursion - Simple and slow approach.
- Dynamic Programming – A judicious and competent approach
Now, let us understand the recursive approach and its limitations which led to another solution to the same problem which is the development of a dynamic programming approach.
A recursive approach to solving Coin Change
Let the array of coins be
- coins[] = {1, 2, 3}
- sum = 4
Two operations can be performed on these coins- they can either be included or excluded.
When the coin is included, its value is added to the current sum solution, that is
(sol + coins [i], I, and if the resultant value is not equal to the target sum, you pass to the subsequent coin, i.e., the subsequent recursive call solution (sol, i++).
Implementation:
File name – Coin.java
// Recursive approach for
// coin change problem in java.
import java.util.*;
class Coin {
// Returns the count of ways we can
// sum coins[0...n-1] coins to get sum "sum"
static int no_of_coins(int coins[], int num, int sum)
{
// If the sum is 0 then only 1 solution exists
// (do not include any coin)
if (sum == 0)
return 1;
// If the sum is less than 0 then no
// solution exists
if (sum < 0)
return 0;
// If no coins are there and the sum
// is greater than 0, then no
// solution exist
if (num <= 0)
return 0;
// count variable denotes the sum of solutions
return no_of_coins(coins, num - 1, sum)
+ no_of_coins(coins, num, sum - coins[num - 1]);
}
// Driver code
public static void main(String args[])
{
int coins[] = { 1, 2, 3, 5, 7, 8 };
int num = coins.length;
System.out.println("Total number of solutions are: ");
System.out.println(no_of_coins(coins, num, 6));
}
}
Output:
The above recursive method causes the algorithm to compute the same subproblems several times. Therefore, in order to solve the coin change problem proficiently, the Dynamic Programming approach needs to be taken into account.
Coin Change Problem Solution Using Dynamic Programming approach
Implementation:
File name – CoinChangeProblem.java
/* Dynamic Programming approach to solving Coin
Change problem in java*/
import java.util.Arrays;
class CoinChangeProblem {
static long count(int coins[], int num, int sum)
{
long[] table1 = new long[sum + 1];
// let all the table values be initialized by 0
Arrays.fill(table1, 0);
// Base case (when the given value is 0)
table1[0] = 1;
// Traverse the coins one by one and keep updating the table[]
// values after the index greater than or equal to
// the value of the picked coin
for (int j = 0; j < num; j++)
for (int k = coins[j]; k <= sum; k++)
table1[k] += table1[k - coins[j]];
return table1[sum];
}
// Driver Function to test the above function
public static void main(String args[])
{
int coins[] = { 1, 2, 3, 5, 7, 8 };
int num = coins.length;
int sum = 6 ;
System.out.println("Total number of solutions are: ");
System.out.println(count(coins, num, sum));
}
}
Output:
The time complexity of this function: O(num * sum)
The space Complexity of this function: O(sum)
Space optimized solution
Implementation:
The following steps need to be followed to implement the idea:
- Initialize the linear array table with zeroes.
- With sum = 0, there is a way.
- Update the level-wise quantity of ways of coin till the ith coin.
- Keep solving until j <= sum.
File name - CoinChangeProblem.java
/* Dynamic Programming approach to solving Coin
Change problem in java*/
import java.util.Arrays;
class CoinChangeProblem {
static long count(int coins[], int num, int sum)
{
// table[i] will store the number of solutions
int table1[] = new int[sum + 1];
// Base case (If the given value is 0)
table1[0] = 1;
// traverse all coins one by one and keep updating the table[]
for (int j = 0; j < num; j++)
for (int k = coins[j]; k <= sum; k++)
table1[k] += table1[k - coins[j]];
return table1[sum];
}
// Driver Function to check the working of the above function
public static void main(String args[])
{
int coins[] = { 1, 2, 3, 5, 7, 8 };
int num = coins.length;
int sum = 6;
System.out.println("The total number of solutions are: ");
System.out.println(count(coins, num, sum));
}
}
Output:
Time Complexity: O(num*sum)
Space Complexity: O(sum)
Coin change using the Top Down (Memoization) Dynamic Programming:
Implementation:
The following steps need to be followed to implement the idea:
- Store the Overlapping subproblems by means of a 2-D vector.
- Pass through the entire array to find the solution and store it in the memorization table.
- Use the memorization table to get the optimal solution.
File name - CoinChangeProblem.java
/* Dynamic Programming approach to solving Coin
Change problem in java*/
import java.util.*;
class CoinChangeProblem {
static int coin(int[] ar, int v1, int n1, int[][] dp1)
{
if (v1 == 0)
return dp1[n1][v1] = 1;
if (n1 == 0)
return 0;
if (dp1[n1][v1] != -1)
return dp1[n1][v1];
if (ar[n1 - 1] <= v1) {
// Either choose this coin or don’t
return dp1[n1][v1]
= coin(ar, v1 - ar[n1 - 1], n1, dp1)
+ coin(ar, v1, n1 - 1, dp1);
}
else // discard this coin
return dp1[n1][v1] = coin(ar, v1, n1 - 1, dp1);
}
// Driver code to check the working of the above function
public static void main(String[] args)
{
int tc1 = 1;
while (tc1 != 0) {
int n1, v1;
n1 = 6;
v1 = 6;
int[] ar = { 1, 2, 3, 5, 7, 8 };
int[][] dp = new int[n1 + 1][v1 + 1];
for (int[] row : dp)
Arrays.fill(row, -1);
int ans = coin(ar, v1, n1, dp);
System.out.println("The total solution are: ");
System.out.println(ans);
tc1--;
}
}
}
Output:
Time complexity: O(num*sum)
Space complexity: O(num*sum)
Applications of Coin Change Problem
This algorithm can be efficiently used to distribute change,
for example, in a soda vending machine that accepts bills and coins and distributes coins.
Buying a 60-cent soda pop with a dollar is one example. This leaves 40 cents to change, or in the United States, one quarter, one dime, and one nickel for the smallest coin pay. However, if the nickel tube were empty, the machine would distribute four dimes.