leetcode_gym/_problems/coinChange.md

layout, title, last_solved, category, leetcode_url, status

layout	title	last_solved	category	leetcode_url	status
page	Coin Change	2020-07-17, 2020-08-25	dp [bottom up]	https://leetcode.com/problems/coin-change	Solved

You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.

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

The solution is to build an array where the current index tells you what's the minimum # of coin for the current index(amount). Ie: arr[2] = 1 will mean 1 coin is needed for $2.

The key formula is min_coins[i] = min(min_coins[i], min_coins[i - c] + 1)

This video actually does the best job at explaining the bottom up approach.

{% highlight python %}

def coinChange(self, coins: List[int], amount: int) -> int:
    
    dp = [0] + [float('inf')] * amount
    
    for a in range(1, amount+1):
        for c in coins:
            if a-c>=0:
                dp[a] = min( dp[a], dp[a-c]+1 )
    
    print(dp)
    
    return dp[-1] if dp[-1]!=float('inf') else -1

{% endhighlight %}