Coin Change Problem is also known as Making Change Problem.
The change-making problem, also known as the minimum coin change problem, addresses the question of finding the minimum number of coins (of certain denominations) that add up to a given amount of money. It is a knapsack type problem and has applications wider than just currency.
It is also the most common variation of the coin change problem, a general case of partition in which, given the available denominations of an infinite set of coins, the objective is to find out the number of possible ways of making a change for a specific amount of money, without considering the order of the coins.
It is weakly NP-hard but may be solved optimally in pseudo-polynomial time by dynamic programming.
We will first solve it by using Recursion:
package dp;
public class CoinChange {
public static void main(String[] args) {
int[] arr = new int[]{1, 2, 3};
int m = 4;
long startTime = System.nanoTime();
System.out.println(TotalPossibleWays(arr, arr.length, m));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
private static int TotalPossibleWays(int[] arr, int length, int m) {
//if sum is 0 then only 1 ways is possible
if(m == 0)
return 1;
//if sum is negative then no ways is possible
if(m < 0)
return 0;
//if all coins used but we didn't get the required sum, then no ways is possible.
if(length<=0 && m >= 1)
return 0;
//Taking all possible ways, once by taking the coin and once by ignoring it.
return TotalPossibleWays(arr, length-1, m) + TotalPossibleWays(arr, length, m-arr[length-1]);
}
}
output:
4
Total Time (nanoseconds) : 424023
If you look carefully we are solving the same subproblem again and again and the time complexity of the above solution is exponential, i.e O(2^n)
Can we make our solution better?
Yes by using Dynamic Programming.
package dp;
public class CoinChange {
public static void main(String[] args) {
int[] arr = new int[]{1, 2, 3};
int m = 4;
long startTime = System.nanoTime();
System.out.println(TotalPossibleWays(arr, arr.length, m));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
private static int TotalPossibleWays(int[] arr, int length, int m) {
//if sum is 0 then only 1 ways is possible
if(m == 0)
return 1;
//if sum is negative then no ways is possible
if(m < 0)
return 0;
int[][] dp = new int[length+1][m+1];
//initialize base values in dp table
for(int i=0;i<arr.length+1;i++)
dp[i][0] = 1;
for(int i=0;i<m+1;i++)
dp[0][i] = 0;
for(int i=1;i<arr.length+1;i++) {
for(int j=1;j<m+1;j++) {
if(j<arr[i-1])
dp[i][j]= dp[i-1][j];
else
dp[i][j]= dp[i-1][j] + dp[i][j-arr[i-1]];
}
}
return dp[length][m];
}
}
output:
4
Total Time (nanoseconds) : 346996
The Time complexity of the above solution is O(n^2) since we are using 2 loops for computation.
