LC322 - Coin Change

Problem

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.

Example

Input: coins = [1,2,5], amount = 11

Output: 3

Explanation: 11 = 5 + 5 + 1

Solution

Intuition

Intuitively, we would first think of a greedy algorithm, but this would not work because using the largest coins might not always lead to the least amount of coins being used, since the remainder must be serviced by more smaller coins than the optimal solution.

Brute Force

Evaluate all the possible selections of coins, which is $O(S^n)$ in time complexity, where S is the amount and n is the size of the coins. The advantage of this approach is that it does not use any additional memory.

Subtree Caching

When we consider the brute force solution, we can notice that we repeatedly evaluate the same subproblem of how many coins are required to cover the remaining amount. This amount can appear in multiple subtrees, and hence caching the results works to save compute at the expense of some memory.

Dynamic Programming

We can use a bottom-up approach to calculate the minimum amount of coins, using the results of previous paths to save computation. Time and space complexity is $O(n)$.

def coinChange(self, coins: List[int], amount: int) -> int:
	dp = [amount+1] * (amount + 1)
	dp[0] = 0

	for cur in range(1, amount+1):
		for coin in coins:
			if cur - coin >= 0:
				dp[cur] = min(dp[cur], 1 + dp[cur - coin])
	
	if dp[amount] != amount+1:
		return dp[amount]
	else:
		return -1