LeetCode 322: Coin Change - Red-Green-Code

LeetCode 2021

Problem

Problem Statement: You are given a set of coin denominations (integers) and an amount of change to make using only these coins. Return an integer representing the smallest number of coins sufficient to make the given amount of change. You may use as many coins of each denomination as you want. If the amount of change is impossible to make using the given coins, return -1.

Solution

This is based on a solution by Stefan Pochmann.

Coin Change is a classic dynamic programming problem. As usual for DP problems, we’ll store earlier results in an array and use them to efficiently calculate later results.

Let amount be the amount of change we need to make. Define an integer array dp[amount+1]. For each amount a, dp[a] is the minimum number of coins sufficient to make a using the coins we have checked so far. We’ll make a pass through dp for each coin denomination, updating it if we get a better result by including that coin.

The base case is dp[0] = 0, since zero coins of any denomination are sufficient to make zero dollars. For every other amount dp[i], we’ll initialize the array with dp[i] = amount+1. This is just an out-of-range value (coin values are integers no smaller than 1, so we’ll never need more than amount of them). When we’re done, the return value will be stored in dp[amount]. If dp[amount] == amount+1, there is no possible answer, so we return -1.

Once the array is initialized, we’ll update it using each coin value. Consider a coin with value c. To make an amount c, we need only one coin with that value, so dp[c] = 1. To make an amount 2c using only that coin, we need two copies of the coin, so dp[2c] = 2, and so on. Continue until the end of the array. At this point, dp stores the minimum number of c coins necessary to make each amount from 0 to amount, if it’s possible to make that amount using only c. Amounts that aren’t possible still have the initialized value, amount+1.

Now consider a second coin with value d, where c != d. To make the amount c+d using these two coins, the best we can do is use one c coin and one d coin, so dp[c+d] = 2. But making the amount c+2d doesn’t necessarily require three coins. For example, if c = 2 and d = 1, then we can make the amount 4 using just two c coins, which is a better result. To ensure that each dp[i] always contains the best result we have found so far, we need to store the smaller of these two coin counts at each step:

Count 1: the value already in dp[i], which is the minimum coin count calculated so far for amount i.
Count 2: dp[i-c] + 1. The current minimum count for amount i-c, plus one more coin of value c, gives us an amount i and a new count for dp[i].

Since we store the minimum value at each step and we only check one coin at at time, it doesn’t matter what order we check the coins in. We’ll get the same result when we’re done with the whole coin list regardless of whether we process the coins in sorted order, reverse sorted order, or any other order.

Pseudocode

Inputs:

coins: an array of integers.

amount: the target amount

define an integer array dp of size amount+1
initialize each element of dp to amount+1
initialize dp[0] to 0

for each coin c
    for each i from c to amount
        set dp[i] to the minimum of dp[i] and dp[i-c] + 1

if dp[amount] is amount+1, return -1
else return dp[amount]

Code

Coin Change on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.