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 number of ways 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 number of ways to making change for 4

  • Expected output: 4

  • Explanation: those 4 ways are {1, 1, 1, 1}, {1, 1, 2}, {1, 3} and {2, 2}

Dynamic Programming Approach

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

  • For each coin in the set c[i], calculate the ways of making change w[j] = w[j] + w[j - c[i]] with c[i] <= j <= target, w[0] = 1 is base case, w[target] is the final result

import java.util.Arrays;

public class DP_CoinChange {  
    static int countWays(int[] coins, int targetCoinChange) {
        int[] wayOfCoinChanges = new int[targetCoinChange+1];

        wayOfCoinChanges[0] = 1;

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= targetCoinChange; j++) {
                wayOfCoinChanges[j] += wayOfCoinChanges[j - coins[i]];
            }
            System.out.println(Arrays.toString(wayOfCoinChanges));
        }

        return wayOfCoinChanges[targetCoinChange];
    }

    public static void main(String[] args) {
        System.out.println(countWays(new int[]{2, 3, 1}, 4));
    }
}
  • 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