HelloKoding

Practical coding guides

Coin Change Problems

In this article, you will learn to analyze and resolve the Coin change problems by using a Dynamic programming algorithm

Problem 1: Count ways of coin change

  • 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 1

  • 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}

Approach 1: Dynamic programming

  • 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

DP_CoinChange.java

package com.hellokoding.algorithm;

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: O(nm) with n is the change target, m is the number of coins
  • Space complexity: O(n) with n is the change target

Problem 2: Minimum coin change

  • 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 2

  • 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}

Approach 2: Dynamic programming

  • 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

DP_CoinChange2.java

package com.hellokoding.algorithm;

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: O(nm) with n is the change target, m is the number of coins
  • Space complexity: O(n) with n is the change target
Follow HelloKoding