Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [1,2,3], amount = 5
Output: 2
Explanation: 5 = 2+3
No of ways to make the change are : { 1,1,1,1,1} , {1,1,1,2}, {2,2,1},{1,1,3} and {3,2}.
So as we can see minimum number of coins required are 2 ( 3+2=5}.

Note

There is another simpler version or variant of the problem Coin Change with Fewest Number of Coins Given Canonical System and Infinite Supply. We will solve generic case here, but the canonical system is easier to solve with greedy approach.

Solution

For every coin, we have two choices: either to include it or exclude it. Thus, we can evaluate both scenarios and select the optimal solution, which in this context is the minimum among all possible solutions.

To solve this, we first decompose the problem into smaller subproblems. But what exactly are these subproblems?

Method 1 - Recursion

Let’s say we have a set of 4 coins: {1, 5, 10, 25}, representing a penny, nickel, dime, and quarter respectively. To find the solution, we need to determine which of the following is the minimum: using a penny plus the number of coins required for the remaining amount after a penny is subtracted, using a nickel plus the number of coins for the remaining amount after subtracting five cents, using a dime plus the number of coins for the remaining amount after ten cents, and so forth. The number of coins needed for the original amount is thus calculated as follows:

$$ numCoins = \begin{cases} 1 + numCoins(originalAmount - 1) \ 1 + numCoins(originalAmount - 5) \ 1 + numCoins(originalAmount - 10) \ 1 + numCoins(originalAmount - 25) \ \end{cases} $$

Code

Java
public class Solution {
    public int coinChange(int[] coins, int amount) {
        // base case
        if (amount == 0) {
            return 0;
        }

        // Initialize result
        int ans = Integer.MAX_VALUE;

        // Try every coin that has smaller value than V
        for (int coin : coins) {
            if (amount - coin >= 0) {
                int currResult = coinChange(coins, amount - coint);

                // Check for INT_MAX to avoid overflow and see
                // if result can minimized
                if (currResult != Integer.MAX_VALUE && currResult + 1 < ans) {
                    ans = ans + 1;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^V) where n is number of coins and V is the amount
  • 🧺 Space complexity: O(V)

However, this algorithm is highly inefficient. For instance, if we need to make change for 26 cents (V = 26), the recursion tree would appear as follows:

In the image we can see that tree is expanding at least 3 times from 15 itself, so that is really inefficient.

The time complexity of above solution is exponential. Every coin has 2 options, to be selected or not selected.

Method 2 - Top Down DP

To improve the efficiency, we use memoization to store the results of subproblems that have already been computed. This helps avoid re-computation and reduces the time complexity.

Code

Java
public class Solution {
    private Map<Integer, Integer> memo = new HashMap<>();

    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;        
        }
        if (memo.containsKey(amount))
            return memo.get(amount);

        int result = Integer.MAX_VALUE;

        for (int coin : coins) {
            if (amount - coin >= 0) {
                int subResult = coinChangeTopDownDP(coins, amount - coin);

                if (subResult != Integer.MAX_VALUE && subResult + 1 < result) {
                    result = subResult + 1;
                }
            }
        }

        memo.put(amount, result == Integer.MAX_VALUE ? -1 : result);
        return memo.get(amount);
    }
}

Complexity

  • ⏰ Time complexity: O(V*n)
  • 🧺 Space complexity: O(V)

Method 3 - Bottom up DP

Let’s see how we can apply dynamic programming (DP) to solve this problem effectively.

1. Optimal Substructure

Given coin denominations coins[] and the target amount A, we recognize that we can build the solution using the substructure property. Here’s a revised view:

minCoins(coins[], A) =
	Base conditions:
	if (A == 0)         => 0
	if (A < 0)          => Integer.MAX_VALUE
 
	Recurrence relation:
	min(minCoins(coins, A - coins[i]) + 1) for all coins[i] such that coins[i] <= A

2. Overlapping Subproblems

With a naive recursive implementation, we would repeatedly calculate the same subproblems which is inefficient. Here’s how we can use dynamic programming:

for all i from 0 to amount:
	for all coin in coins:
		if (i - coin >= 0)
			dp[i] = min(dp[i], dp[i - coin] + 1)
  • dp[i] represents the minimum number of coins needed to make the amount i.
  • For each coin, if we include the coin in the solution, we add 1 to the result of dp[i - coin].

Detailed Steps

  • We maintain an array dp[] where dp[i] represents the minimum number of coins needed for the amount i.
  • Initialize dp[] with a high value (e.g., Integer.MAX_VALUE) and set dp[0] to 0 since no coins are required to make an amount of 0.
  • Using a bottom-up approach, we fill out the array dp[] for all values from 0 to amount.
  • The final solution will be in dp[amount] which will give us the minimum number of coins required to make the amount n. If it remains as Integer.MAX_VALUE, it means the target amount cannot be made with the given denominations.

Code

Java
Without Sorting
public class Solution {
    public int coinChange(int[] coins, int amount) {
        // this will store the optimal solution
        // for all the values -- from 0 to given amount.
        int[] dp = new int[amount+1];
        dp[0] = 0; // 0 coins are required to make the change for 0 (no need to set as default val is already 0 but for clarity)
        // now solve for all the amounts
        for (int a = 1; a <= amount; a++) {
            dp[a] = Integer.MAX_VALUE; // initially we don't know solution, hence ∞
            // Now try taking every coin one at a time and pick the minimum
            for (int coin: coins) {
                if (coin <= a && dp[a - coin] != Integer.MAX_VALUE) { // check if coin value is less than amount
                    // select the coin and add 1 to solution of (amount-coin value)
                    dp[a]= Math.min(dp[a], 1 + dp[a - coin]);
                }
            }
        }
        //return the optimal solution for amount
        return dp[amount] != Integer.MAX_VALUE ? dp[amount]: -1 ;

    }
}
With Sorting

We can improve the speed a bit, if we sort the coins denominations:

public int minCoinsDP2Optimized( int[] coins, int amount) {
	Arrays.sort(coins); // sort the denominations
	int[] dp = new int[amount + 1]; // stores the min number of coins
	Arrays.fill(dp, amount+1); // default integer value in array is not good

	dp[0] = 0;
	for (int i = 0; i <= amount; ++i) {
		for (int j = 0; j < coins.length; j++) {
			if (coins[j] <= i) {
				dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);
			}else {
				break; // coins array is already sorted
			}
		}
	}

	return dp[amount] > amount ? -1 : dp[amount];
}

Complexity

  • ⏰ Time complexity: O(V*n)
  • 🧺 Space complexity: O(V)

Time complexity of the above solution is O(mV). V=value for whcih change is needed, m = number of denims

Dry Run

Let’s dry run the code for amount = 13 and coins = [7, 2, 3, 6] using the bottom-up dynamic programming approach.

Initial Setup
  1. Array dp[] Initialization:
    • dp[0] = 0 (0 coins to make amount 0).
    • All other dp[i] initialized to amount + 1 (infinity in this context).
Initial dp Array
 dp = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
Filling dp[] Array

We iterate over each amount from 1 to 13 and for each coin.

Iteration for i = 1
  • Coin = 7: i - coin < 0, no update.
  • Coin = 2: i - coin < 0, no update.
  • Coin = 3: i - coin < 0, no update.
  • Coin = 6: i - coin < 0, no update.
 dp = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
Iteration for i = 2
  • Coin = 7: i - coin < 0, no update.
  • Coin = 2: dp[2] = min(dp[2], dp[2 - 2] + 1) => dp[2] = min(inf, 0 + 1) => 1.
     dp = [0, inf, 1, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
  • Coin = 3: i - coin < 0, no update.
  • Coin = 6: i - coin < 0, no update.
Iteration for i = 3

  • Coin = 7: i - coin < 0, no update.

  • Coin = 2: No update as dp[3 - 2] + 1 continues to result in inf.

  • Coin = 3: dp[3] = min(dp[3], dp[3 - 3] + 1) => dp[3] = min(inf, 0 + 1) => 1.

     dp = [0, inf, 1, 1, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]

  • Coin = 6: i - coin < 0, no update.

Iteration for i = 4
  • Coin = 7: i - coin < 0, no update.
  • Coin = 2: dp[4] = min(dp[4], dp[4 - 2] + 1) => dp[4] = min(inf, 1 + 1) => 2.
     dp = [0, inf, 1, 1, 2, inf, inf, inf, inf, inf, inf, inf, inf, inf]
  • Coin = 3: dp[4] continues to be 2 after attempting to update with dp[1] + 1.
  • Coin = 6: i - coin < 0, no update.
Iteration for i = 5
  • Coin = 7: i - coin < 0, no update.
  • Coin = 2: No update as dp[5 - 2] + 1 continues to result in 2.
  • Coin = 3: dp[5] = min(dp[5], dp[5 - 3] + 1) => dp[5] = min(inf, 1 + 1) => 2.
     dp = [0, inf, 1, 1, 2, 2, inf, inf, inf, inf, inf, inf, inf, inf]
  • Coin = 6: i - coin < 0, no update.
Iteration for i = 6
  • Coin = 7: i - coin < 0, no update.
  • Coin = 2: No update as dp[6 - 2] + 1 continues to be 3.
  • Coin = 3: No update as dp[6 - 3] + 1 continues to be 2.
  • Coin = 6: dp[6] = min(dp[6], dp[6 - 6] + 1) => dp[6] = min(inf, 0 + 1) => 1.
     dp = [0, inf, 1, 1, 2, 2, 1, inf, inf, inf, inf, inf, inf, inf]
Iteration for i = 7
  • Coin = 7: dp[7] = min(dp[7], dp[7 - 7] + 1) => dp[7] = min(inf, 0 + 1) => 1.
     dp = [0, inf, 1, 1, 2, 2, 1, 1, inf, inf, inf, inf, inf, inf]
  • Coin = 2: No update as dp[7 - 2] + 1 continues to be 3.
  • Coin = 3: No update as dp[7 - 3] + 1 continues to be 2.
  • Coin = 6: No update.
Iteration for i = 8

  • Coin = 7: No update.

  • Coin = 2: dp[8] = min(dp[8], dp[8 - 2] + 1) => dp[8] = min(inf, 1 + 1) => 2.

     dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, inf, inf, inf, inf, inf]

  • Coin = 3: No update as dp[8 - 3] + 1 continues to be 3.

  • Coin = 6: dp[8] = min(dp[8], dp[8 - 6] + 1) => dp[8] = min(2, 1 + 1) => 2.

Iteration for i = 9

  • Coin = 7: Update becomes higher, so no change.

  • Coin = 2: No change as dp[9 - 2] + 1 is 2 as well.

  • Coin = 3: dp[9] = min(dp[9], dp[9 - 3] + 1) => dp[9] = min(dp[9], 2) => 2.

  • Coin = 6: dp[9] = min(dp[9], dp[9 - 6] + 1) => dp[9] = min(dp[9], 3) => 3.

     dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, 2, inf, inf, inf, inf]
Iteration for i = 10

  • Coin = 7: Update becomes higher, so no change.

  • Coin = 2: No change as dp[10 - 2] + 1 is 3.

  • Coin = 3: No change as dp[10 - 3] + 1 updates it to 1.

  • Coin = 6: No change as dp[10 - 6] + 1 results the same.

     dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, 2, 2, inf, inf, inf]
Iteration for i = 11

  • Coin = 7: No change as adding increment results higher.

  • Coin = 2: dp[11 - 2] + 1 results the optimal list count.

  • Coin = 3: No change as adding increment results higher.

  • Coin = 6: No change as adding increment results 3.

     dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, 2, 3, 2, inf, inf]
Iteration for i = 12

  • Coin = 7: Update becomes higher, so no change.

  • Coin = 2: Update gets optimal value.

  • Coin = 3: No change as recursion results extra +1.

  • Coin = 6:`dp[12 -6] results the minimum.

     dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, 2, 3, 2, 2, inf]
Iteration for i = 13
  • Coin = 7:-update not needed as recursion count adds the extra.
  • Coin = 2: update returns optimal value as needed.
  • Coin 3: No changes required as list includes the count
  • Coin 6: Update is optional as no list recurrence added.
Final Result`

Finally, our output count returns:

  dp[13]=min(dp[13],dp[6]+1)
 `
 
 Thus dp[13] returns the minimum of 2 - {[7,6]}`

Method 4 - Using Breadth First Search

Most dynamic programming problems can also be solved using BFS.

This problem can be visualised as reaching a target position with steps taken from the array of coins. We use two queues: one to track the current amount and the other for the minimal steps taken.

Dry run with:

amount = 13, coins = [7, 2, 3, 6].

Code

Java
public int coinChange(int[] coins, int amount) {
    if (amount == 0)
        return 0;

    Queue<Integer> amountQueue = new LinkedList<Integer>();
    Queue<Integer> stepQueue = new LinkedList<Integer>();
    Set<Integer> visited = new HashSet<>(); // leveraging optimized contains using Set

    // to get 0, 0 step is required
    amountQueue.offer(0);
    stepQueue.offer(0);
    visited.add(0);

    while (amountQueue.size() > 0) {
        int currAmount = amountQueue.poll();
        int steps = stepQueue.poll();

        if (currAmount == amount) {
            return steps;        
        }

        for (int coin : coins) {
			int newAmount = currAmount + coin;
			if (newAmount <= amount && visited.add(newAmount)) {
				amountQueue.offer(newAmount);
				stepQueue.offer(steps + 1);
			}            
        }
    }

    return -1;
}

Complexity

  • ⏰ Time complexity: O(n * A)
  • 🧺 Space complexity: O(A) for storing amounts and corresponding steps in queue