Coin Change Leetcode


#1

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

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


#2

The below solution uses bottom up approach in DP. Basically calculate the min no of coins required for 1 to amount and return the final value.

Intuition behind the recurrence relation here is,

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

that you either choose the last min value or imagine what would be dp[i] value of coins[j] is not used and add one coin to it. That is why we use the minus of coins[j].

Time Complexity -> O(len(coins)*amount)

Space Complexity -> O(amount+1)

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i:=0; i<len(dp); i++{
        dp[i] = amount+1
    }
    
    dp[0] = 0
    for i:=1; i<=amount; i++{
        for j:=0; j<len(coins); j++{
            if coins[j] <= i  {
                dp[i] = minInt(dp[i], dp[i-coins[j]]+1)
            }
        }
    }
    
    if dp[amount]>amount{
        return -1
    }
    
    return dp[amount]
}

func minInt(a, b int) int {
    if a<b{
        return a
    }
    return b
}