Coin Change

Problem Statement

Given an integer array coins containing different denominations of currency and an integer amount amount representing your total amount of money, return the fewest number of coins needed to represent amount, returning -1 if it is not possible.

Solution

Immediately, DP should stick out as the way forward here. We are trying to find the fewest number of coins possible to represent a value. If you just envision the decision tree here, you can see that there are many branches that are most likely going to be repeated work. Additionally, some other important features of the problem are:

1. We have a collection of items: coins
2. We have a distinct constraint: amount
3. There is no limitation of how many of each coin we can use

These factors all make it very clear that the approach will be Unbounded Knapsack. So, let dp[i] represent the smallest number of coins it takes to make i. Clearly, when can make i with i-c + 1 moves, where c is an arbitrary value in coins. Thus, following the general template for unbounded knapsack, we have our answer:

dp = [float("inf")] * (amount + 1)
dp[0] = 0
for c in coins:
	for i in range(c, amount+1):
		dp[i] = min(dp[i-c] + 1, dp[i])

if dp[amount] != float("inf"):
	return dp[amount]

return -1

• Runtime Complexity: O(amount * n)
• Space Complexity: O(amount)

A quick note, you may be wondering why we don't loop over the coins array and establish base cases like this:

for c in coins:
	dp[c] = 1

While this would still work and is intuitive, the inner loop does this by itself through the first assignment in each iteration:

dp[c] = min(0 + 1, float("inf"))