In this article, we will learn to resolve the Coin Change problem in Java by using a dynamic programming algorithm

Problem

  • Given a set of infinite coins

  • Find the minimum number of coins to making change for a specific amount of money, without considering the order of the coins

Example

  • Input: given a set of infinite coins {2, 3, 1}. Find the minimum number of coins of making change for 3

  • Expected output: 1

  • Explanation: there're 3 ways to making change for 3: {3}, {1, 1, 1}, {1, 2}, minimum is {3}

Dynamic Programming Approach

  • To making change for a value i, need to use coins with a value less than or equal to i

  • For each coin in the set c[j], calculate the minimum number of coins to making change m[i] = Math.min(m[i], m[i - c[j]]) + 1 with c[j] <= i <= target, m[0] = 0 is base case, m[target] is the final result

import java.util.Arrays;

public class DP_CoinChange2 {  
    static int countMin(int[] coins, int targetCoinChange) {
        int[] minNoOfCoins = new int[targetCoinChange+1];
        Arrays.fill(minNoOfCoins, targetCoinChange + 1);

        minNoOfCoins[0] = 0;

        for (int i = 1; i <= targetCoinChange; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    minNoOfCoins[i] = Math.min(minNoOfCoins[i], minNoOfCoins[i - coins[j]] + 1);
                }
            }
        }

        return minNoOfCoins[targetCoinChange] > targetCoinChange ? -1 : minNoOfCoins[targetCoinChange];
    }

    public static void main(String[] args) {
        System.out.println(countMin(new int[]{2, 3, 1}, 3));
    }
}
  • Time complexity is O(nm) and space complexity is O(n) where n is the change target, m is the number of coins

References

AlgorithmDynamic Programming