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) | – |