322. 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.

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

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

This is a problem with the optimal substructure property, and therefore DP seems like a good approach. For example, take the set of coins [1, 2, 5]. To calculate the fewest number of coins we need to make 73, we can try three options:

• We can do the fewest number of coins to make 72 and add a $1 coin.
• We can do the fewest number of coins to make 71 and add a $2 coin.
• We can do the fewest number of coins to make 68 and add a $5 coin.

The optimal answer is the one that uses the fewest coins overall—and if it isn’t possible for any of them, then there is no way for us to make 73 anyways! Our base cases come from coins—we need one coin, a single $5 coin, to make $5—and the fact that we need 0 coins to make 0. The Bellman Equation takes shape:

Bottom-Up

The trickiest part occurs in the recursive case. We must check for the minimum recursive case, but only for those that have a previous solution or results in a possible combination. If there is none, we by default set it to -1 to indicate that it is not possible to make this number using our coin set.

def coinChange(coins: List[int], amount: int) -> int:
	solutions = {}
	
	for i in range(amount + 1):
		if i == 0:
			solutions[i] = 0
		elif i in coins:
			solutions[i] = 1
		else:
			solutions[i] = min((solutions[i - c] + 1 
				for c in coins 
				if i - c in solutions and solutions[i - c] != -1), 
				default=-1
			)
	
	return solutions[amount]

Notice that even though we go from 0 up to amount in the loop, we still need to check if i - c in solutions. This is because we can end up before 0. Consider the set of coins [2, 5] and $OPT(1)$: we would check $OPT(1 - 2) = OPT(-1)$ and $OPT(1-5) = OPT(-4)$.

Top Down

def coinChange(coins: List[int], amount: int) -> int:
	solutions = {}
	
	def makeChange(amount: int) -> int:
		if amount in solutions:
			return solutions[amount]
	
		if amount < 0:
			return -1
		elif amount == 0:
			return 0
		elif amount in coins:
			return 1
		
		bestChange = float('inf')
		for coin in coins:
			sub = makeChange(amount - coin)
			if sub != -1:
				bestChange = min(bestChange, sub + 1)
				
		solutions[amount] = bestChange if bestChange != float('inf') else -1
		return bsolutions[amount]
			
	return makeChange(amount)

Time Complexity

Notice in both solutions, we make $\mathcal{O}(n)$ iterations. In each iteration, there are some constant time operations, and then a for loop on the coins. Each iteration of that for loop is constant time, so each iteration of the solution takes $\mathcal{O}(m)$ time where $m$ is the number of coins. Therefore the total time complexity is in $\mathcal{O}(nm)$.

Space Complexity

We memoise one variable for at most $n$ calculations, so the total space complexity is in $\mathcal{O}(n)$.