Dynamic Programming. Coin Change

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.

A real world example of this problem is a cashier working in the gas station, who want to give out minimum of the coins as possible.

Let's brainstorm a logic how we can solve it?

we have to make up to a certain amount.

For example:

let's say we have to give 11$. let's see how we can return 11$ in minimum coin?

Input: coins = [1,2,5], amount = 11

we have 1, 2 and 5 as an option

we have following option

1 $ coin * 11(times) = 11$, => total 11 coins

2 $ coin * 5(times) = 10 + 1 coin = 11$, => total 6 coins

5 $ coin * 2(times) = 10 + 1$ coin = 11 $, => total 3 coins

thus, we'd return only 3 coins of two 5$ coins and one 1$ coin.

let's see what was the thinking process behind it?

1. we had to build the amount from 1 to the total amount
2. We need to calculate and compare all of our given coins trying to make up to the total amount

These two things are certain. Let's see how we can build from it?

from number 1 point:

for( let amount = 1 ; amount <=totalMoneyToReturn; amount++){
}

from 2:

We need to iterate and weigh all of our coins and compute the minimum coins to return

Coins.forEach(coin => how many coins needed to make the total )

now let's see how we can combine these two:

for( let currentAmount=0;currentAmount<= amount;currentAmount){
    coins.forEach(coin =>{
  
     })
}

Now,

let's use this example again:

Input: coins = [1,2,5], amount = 11

let's have a variable, which will store the minimum amount of coins needed to return the amount A, in the position a.

let's assume, we first need to return 0

amount 0 1 2 3 4 5 6 7 8 9 10

let minmumCoinArray = [0, 0, 0, 0, 0 , 0 , 0, 0, 0, 0, 0 ]

let's see here

1. To return 0$ amount it takes 0 coin. minimumCoinArray[0]= 0
2. To return 1$ amount we can look up to the coin array
3. with coin of 1$, minimumCoinArray[1] = 1
4. with coin of 2$ and 5$, it's not valid
5. To return 2$ amount, we can again look up to the coin array,
6. options
7. two coins of 1$
8. one coin of 2$
9. 5$ in invalid option
10. Now let's see which option to return, since we wanna use minimum coins we need to return 1.
11. Thus, Math.min is also required for the calculation
12. minimumCoinArray[0]= Math.min(1, 2)
13. To return 3$ amount
14. options:
15. three coins of 1$
16. one coin of 2$ + 1 more coin of 1$
17. 5$ is invalid
18. Math.min(3, 2) = 2 coins
19. To return 4$ amount
20. options:
21. array[4] = Math.min(array[4 -1] + 1, array[4])
22. array[4] = Math.min(array[4 -2] + 1, array[4])
23. 5 is invalid again
24. min to make 4
25. Math.min
26. coins : (amount @ [4-1] + coin
27. coins: (amount @ [4-2] + coin
28. 5$ is still invalid

Easy to understand break down

Imagine you have a friend, and you ask them:

"Hey, if you had to pay 7 units with denominations 1, 2, and 5, what's the least number of coins you'd use?"

Day 1 - Your friend only remembers 1-unit coins:

To pay 1 unit, they'd use 1 coin of 1 unit.

To pay 2 unit, they'd use 2 coin of 1 unit

To pay 3 unit, they'd use 3 coin of 1 unit

To pay 7 unit, they'd use 7 coin of 1 unit

Your friend records this on a piece of paper:

Amount Coins Needed (just using 1s)

1 1 coins

2 2 coins

3 3 coins

4 4 coins

5 5 coins

7 7 coins

Day 2 - Your friend recalls the existence of the 2-unit coin:

Now, they think, "What if I use the 2-unit coin for each amount?"

dp[each amount i,e i]

Amount Coins Needed (just using 1s)

1 1 coins

2 1 coins ====> (1 + 0 )coins

3 3, (2 + 1 ) = 2 coins ====> (1 + 1 )coins

4 4, (2 + 2) = 2 coins ====> (1 + 1 )coins

5 5, ( 2 + 2 + 1) = 3 coins ====> (1 + 2 )coins

7 7, ( 2 + 2 + 2 + 1) = 4 coins ====> (1 + 3 )coins

Day 3 - Your friend recalls the 5-unit coin:

This time, they compare the results using the 5-unit coin against the previous best results.

dp[each amount i,e i]

Amount Coins Needed (just using 1s)

1 1

2 1

3 3, (2 + 1 ) = 3 coins

4 4, (2 + 2) = 2 coins

5 5, instead of using 3 coins, we will only use 1 coin of 5 units

7 7, instead of using 4 coins, we will only use 2 coins of 5 units + 1 coin of 2 units

here we are updating our memory with new calculation so this is sort of dynamic programming.

What't the recurrence relation?

For each amount, the way we are deriving the relation is:

whatever is the minimum of either

1. previous result i.e dp[i]

2. current coin + best way of paying the rest of the amount

i.e 1 + dp[i - coin]

dp[given amount] = Math.min(dp[given amount], 1 + dp[given amount - coin])

So here we know:

1. We need to iterate over the coins

2. We need to iterate over the amounts

        for (i = 0; i <= amount; i++) {
            for(coin of coins){
/*
 and the only time we are going to update the dp[i] is when
the current coin is less than or equal to the amount
*/

            if (coin <= i) {
                dp[i] = Math.min(dp[i], 1 + dp[i - coin])
            }
        }

so the actual code is

function coinChange(coins, totalAmount) {
    if(coins.length === 0){
        return -1
    }
    const dp = new Array(totalAmount + 1).fill(Infinity)
    dp[0] = 0
    for (let i = 0; i <= totalAmount; i++) {
       for(let coin of coins){
        if(i - coin >= 0){
            dp[i] = Math.min(dp[i - coin] + 1, dp[i])
          }
        }
    }
    return dp[totalAmount] === Infinity ? -1: dp[totalAmount]
}

What are the complexities of this code?

Time Complexity = O(M * Amount), where M is total number of different coins

Space Complexity = O(Amount)

after submitting to Leetcode: