Coin Change

Medium

The problem

You have unlimited coins of each value in coins. Return the fewest coins needed to make exactly amount, or -1 if it cannot be done.

Example 1
Input: coins = [1, 2, 5], amount = 11
Output: 3
5 + 5 + 1.
Example 2
Input: coins = [2], amount = 3
Output: -1
Coins of 2 can only make even amounts.
Example 3
Input: coins = [1], amount = 0
Output: 0
You need no coins to make 0.

Limits

1 ≤ len(coins) ≤ 12
1 ≤ coins[i] ≤ 10,000
0 ≤ amount ≤ 10,000

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

The fewest coins for amount a = 1 + the fewest coins for (a − some coin).

The idea

dp[0]=0; dp[a] = 1 + min(dp[a−c]) over coins c ≤ a; unreachable stays at infinity.

Target: O(amount · coins) time

Go function shape

func coinChange(coins []int, amount int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// CoinChange: fewest coins that make up amount, or -1.
// State: dp[a] = fewest coins for amount a. Order: small amounts first.
func CoinChange(coins []int, amount int) int {
	inf := amount + 1 // larger than any real answer
	dp := make([]int, amount+1)
	for a := 1; a <= amount; a++ {
		dp[a] = inf
		for _, c := range coins {
			if c <= a {
				dp[a] = min(dp[a], dp[a-c]+1)
			}
		}
	}
	if dp[amount] >= inf {
		return -1
	}
	return dp[amount]
}

Read the lesson: Dynamic Programming