LeetCode #322 Coin Change Detail Explained

Difficulty: Medium

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

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

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Example 4:

Input: coins = [1], amount = 1
Output: 1

Example 5:

Input: coins = [1], amount = 2
Output: 2

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

The first thing came up in my mind is greedy solution. I tried and realized I got wrong answer. Basically the method is to go from the largest coin, minus the amount, then go to the next biggest (but smaller or equal to the amount left) and minus that. However, for example, when we have coins of [1, 3, 4, 5] and we try to get amount of $7, this will give us a wrong result because it will first encounter $5, then it will choose to use 2 $1s which is a total of 3 coins. But we all can tell $3 + $4 is the best combo and the result should be 2.

decision tree

Then we can start trying to draw the decision tree. This is considered to be a “top — down” approach.

However by looking at these graphs we can realize that lots of the stuff is the same. For example when we are trying to find out what is the minimum number of coins to make up a 3, we will always come down to the same solution which is just 1 $3 coin. Therefore, we can try to optimize the solution by using caching.

We can then create an array of size amount + 1 and fill the array by the value amount + 1 for all of them (the reason that we use amount + 1 not 0 will be revealed at the end).

DP bottom — up solution

Then we start from dp[0]. i means the kind of amount we are trying to make by using coins and dp[i] means the minimum number of coins we need in order to make that amount.

So, we will go from dp[0] and all the way to dp[amount]. In each round, we will try all coins from coins array, make sure whenever we encounter a coin combination that is lower than the current dp[i], we update it.

Input: coins = [1, 3, 4, 5], amount = 7
Output: 2
for (int c : coins) {
    if (i - c >= 0) 
        dp[i] = Math.min(dp[i], 1 + dp[i - c];
}

This is exactly how we will do it. for clarity we can assume right now c = 3and i = 7. We are trying to figure out what is the minimum for dp[7]. Since we would already tried c = 1 , right now dp[7] probably equals to 3. the last line just compare with the minimum number we have so far (which is 3) with the new possibility 1 + dp[7–3]. 1 means we use one more $3 coin so thats why the 1 exist, and dp[7–3] means since we already used one $3 coin, we only have $4 left and we want to find out what was the minimum number of coin we need in order to make a $4 amount. And since this had been computed before and stored in there, we can get it instantly and it will be 1. So dp[7] will be 2 because 2 is smaller than 3.

This is really simple code but the thinking is quite hard. I bet Dynamic Programming takes lots of practice to master.

Again screenshot and the whole explanation came from NeetCode on Youtube.