322. Coin Change

Problem

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.

Problem Summary

Given coins of different denominations, coins, and a total amount, amount. Write a function to compute the fewest number of coins needed to make up the total amount. If no combination of coins can make up the total amount, return -1.

Solution Approach

• Given some coins and a total amount, ask what is the minimum number of coins needed to make up this total?
• This problem is the classic coin change problem, solved using DP. However, one test case for this problem has a very large value, so creating a DP array would waste a lot of space. For example, with coin denominations like [1,1000000000,500000], you are asked to make up a total like 2389412493027523. Following the solution below, the array would be very large and waste a lot of space. In this case, using DFS to solve the problem would save some space.

Code

package leetcode

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