Coin Change is the problem of finding the number of ways of making changes for a particular amount of cents, n, using a given set of denominations d{1} dots d{m}.
source Code
package com.dsacode.Algorithm.dynamic;
import java.util.Arrays;
public class CoinChange {
public static int[] minChange(int[] denom, int changeAmount)
{
int n = denom.length;
int[] count = new int[changeAmount + 1];
int[] from = new int[changeAmount + 1];
count[0] = 1;
for (int i = 0 ; i < changeAmount; i++)
if (count[i] > 0)
for (int j = 0; j < n; j++)
{
int p = i + denom[j];
if (p <= changeAmount)
{
if (count[p] == 0 || count[p] > count[i] + 1)
{
count[p] = count[i] + 1;
from[p] = j;
}
}
}
if (count[changeAmount] == 0)
return null;
int[] result = new int[count[changeAmount] - 1];
int k = changeAmount;
while (k > 0)
{
result[count[k] - 2] = denom[from[k]];
k = k - denom[from[k]];
}
return result;
}
public static void main(String[] args) {
int [] arr=minChange(new int[]{1, 2, 5}, 10);
System.out.println("General coin change that keeps track of coins: "+Arrays.toString(arr));
}
}
Output
General coin change that keeps track of coins: [5, 5]
Algorithm Explanation
 | Initialize the coins denominations and sum to the utility function. |
| Create two arrays with change amount and iterate the array till change amount and find the coin change solution. |
| Use dynamic programming to cache the results for sub problems. |
| Return the coin change solution and print the result. |
Time Complexity
| Best Case | Average Case | Worst Case |
|---|---|---|
| – | O(mn) | – |