0322 - Coin Change (Medium)

Problem Link

https://leetcode.com/problems/coin-change/

Problem Statement

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 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

Approach 1: Dynamic Programming

We can create a $dp$ array of length $amount + 1$ to represent all the ways we can make change from $0$ to $amount$, then solve the ways we can make each amount.

We can do this by initializing the array with a number larger than the amount ($amount$ using all $1$ coins would reach size $amount$), and give the $0$ position of the array a value of $0$.

Then we can loop through all amounts, and for each amount, loop through all the coins, and updating the amount at that position with either its current value, $dp[i]$ or the value from $amount - coin$ incremented by $1$.

Time Complexity: $O(amount + len(coins))$. We are going to iterate over each amount, and for each amount, iterate through each coin.

Space Complexity: $O(amount)$. We are going to create an array of size $amount$ to hold the number of ways we can create each amount.

Python

Written by @ColeB2

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # initialize dp array, we will use float('inf') as an initial
        # value, any value over the largest value of amount would work.
        # The array shows the number of ways we can make coins for each
        # value from 0 to amount + 1, which would be our amount.
        dp = [float('inf')] * (amount + 1)
        # The number of ways we can make change for 0.
        dp[0] = 0
        # loop over the dp array, we already handled 0.
        for i in range(1, len(dp)):
            # loop through each coin
            for coin in coins:
                # i - coin is >= 0, we can use it to determine amount
                if i - coin >= 0:
                    # the way to make coins will be either the min of
                    # the current way to make coins, dp[i] or
                    # the number of ways it took to make coins at the 
                    # current amount minus the coin we are using + 1.
                    dp[i] = min(dp[i], 1 + dp[i-coin])
        # return the last number in the array, which will be amount.
        # do so iff that amount does not equal inf.
        return dp[-1] if dp[-1] != float('inf') else -1