Coin Change

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

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

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

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

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

---

The approach that may come to mind right away is to generate all possible sums of the coin denominations for the amount given and return the smallest sum.

However, similar to most backtracking algorithms, that would require exponential time and would be recalculating some of the same values over and over.

A better approach is to use Dynamic Programming so that we can refer back to subproblems that have been calculated prior to avoid recalculating them.

---

Let's start by creating our dp lookup table.

We will initialize each element to be infinity, with the exception of the zeroth index, since we would be using zero coins to make an amount of zero.  This is our base case.

We want to use infinity since it is out of the bounds of our possible amounts, and we can ensure that the coin amounts we will use to overwrite these will be lower in value.

        dp = [0] + ( [float('inf')] * amount)

 

Here is where the bottom-up processing logic will come into play.

We are going to create an outer loop to traverse the coins, an inner loop to traverse from the current coin amount to the amount input, and within the inner loop, we are going to set the value in the current index as the minimum between what it already is, or the value in the index at the current iterator, minus the coin amount, plus one.

So let's explain what this is going to do given the coins of [1,5,10], and the amount of ten.

The lookup table, dp is telling us the minimum possible coin amount for each amount.  In other words, index one holds the minimum amount of coins needed to make one cent, index two for two cents, etc.  

This is how we can break this problem up into subproblems and avoid recalculating the same values.

We will start off at index one and step all the way to the tenth index, dropping pennies at each index.

Our lookup table will look like this after the first pass.

0

1

2

3

4

5

6

7

8

9

10

Once we are done handling pennies, we can grab a handful of nickels to switch with the values from index five onward. There is no point in putting a nickel at any index before five because each of the previous amount values is less than five cents.  

So how many nickels should we put in the index?  That is where our lookup table comes in handy.  

In the line of code given below, we are basically saying that we will either keep the value that we already have, or we will take the value in the current index minus the coin amount, then add one to it.

                dp[i] = min(dp[i], dp[i-coin] + 1)

 

For example, let's say we are at index five.  We had written five in it previously, so that means we had five pennies that we dropped in it from the last pass. 

Should we keep the five pennies, or what dp[i-coin] has, then add one to it?  Well, dp[0] is zero, if we add one then we will have one.  Is one less than five?  Yes, so we remove the five pennies and drop a nickel at index five.  We'll also remove five pennies and drop a nickel from index six through ten as well for the same reason, and afterward, our dp table will look like this.

0

1

2

3

4

1

2

3

4

5

2

 

Lastly, we will see if we can get a lower amount of coins at index ten once we iterate to the dime from our coins input.

0

1

2

3

4

1

2

3

4

5

1

 

Once we are finished, we will either return the last element of the table which contains the number of coins for the target amount given, or a negative one if we weren't able to calculate it.