Coin Change

You are given an integer array coins representing coins of different denominations (e.g. 1 dollar, 5 dollars, etc) and an integer amount representing a target amount of money.

Return the fewest number of coins that you need to make up the exact target amount. If it is impossible to make up the amount, return -1.

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

12 = 10 + 1 + 1. Note that we do not have to use every kind coin available.

The amount of 3 cannot be made up with coins of 2.

Choosing 0 coins is a valid way to make up 0.

Approach

Use bottom-up DP where dp[a] is the minimum coins needed to make amount a. Initialize dp[0] = 0 and the rest to infinity. For each amount, try all coins and take the best.

Why It Works

Every optimal solution for amount a ends with some coin c, so it equals dp[a - c] + 1. The DP considers all coins and amounts in increasing order, guaranteeing the optimal count or determining it is impossible.

Complexity

• Time: O(amount * number_of_coins)
• Space: O(amount)

Reference Implementation (Python)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        INF = amount + 1
        dp = [INF] * (amount + 1)
        dp[0] = 0
        for a in range(1, amount + 1):
            for coin in coins:
                if coin <= a:
                    dp[a] = min(dp[a], dp[a - coin] + 1)
        return -1 if dp[amount] == INF else dp[amount]