The Change Making Problem

Ben explains the change making problem- finding the minimum number of coins that add to a particular amount. The algorithm uses dynamic programming. A Java code sample is provided below.

Table of Contents
Enroll in our 5-day mini coding interview class

Code Sample

/*
Coin Change - LeetCode: https://leetcode.com/problems/coin-change
All credit for code goes to user @elmirap who wrote the solution
section to this problem: https://leetcode.com/problems/coin-change/solution/
The video to explain this code is here: https://www.youtube.com/watch?v=jgiZlGzXMBw
*/
/*
The Top Down Approach
This code passes all Leetcode test cases as of Jan. 10 2019
Runtime: 53 ms
*/
public class CoinChangeTopDown {
public int coinChange(int[] coins, int amount) {
if (amount < 1) {
return 0;
}
return coinChange(coins, amount, new int[amount + 1]);
}
private int coinChange(int[] coins, int remainder, int[] dp) {
/*
Minimum coins to make change for a negative amount is -1.
This is just a base case we arbitrarily define.
*/
if (remainder < 0) {
return -1;
}
/*
The minimum coins needed to make change for 0 is always 0
coins no matter what coins we have.
*/
if (remainder == 0) {
return 0;
}
// We already have an answer cached. Return it.
if (dp[remainder] != 0) {
return dp[remainder];
}
/*
No answer yet. Try each coin as the last coin in the change that
we make for the amount
*/
int minimum = Integer.MAX_VALUE;
for (int coin : coins) {
int changeResult = coinChange(coins, remainder - coin, dp);
/*
If making change was possible (changeResult >= 0) and
the change result beats our present minimum, add one to
that smallest value
We accept that coin as the last coin in our change making
sequence up to this point since it minimizes the coins we
need
*/
if (changeResult >= 0 && changeResult < minimum) {
minimum = 1 + changeResult;
}
}
/*
If no answer is found (minimum == Integer.MAX_VALUE) then the
sub problem answer is just arbitrarily made to be -1, otherwise
the sub problem's answer is "minimum"
*/
dp[remainder] = (minimum == Integer.MAX_VALUE) ? -1 : minimum;
// Return the sub problem's answer
return dp[remainder];
}
}
/*
The Bottom Up Approach
This code passes all Leetcode test cases as of Jan. 10 2019
Runtime: 31 ms
*/
public class CoinChangeBottomUp {
public int coinChange(int[] coins, int amount) {
// We use this to fill the dp table with default values
int max = amount + 1;
// This table will store the answer to our sub problems
int[] dp = new int[amount + 1];
// Initialize the dp table
Arrays.fill(dp, max);
/*
The answer to making change with minimum coins for 0
will always be 0 coins no matter what the coins we are
given are
*/
dp[0] = 0;
// Solve every subproblem from 1 to amount
for (int i = 1; i <= amount; i++) {
// For each coin we are given
for (int j = 0; j < coins.length; j++) {
// If it is less than or equal to the sub problem amount
if (coins[j] <= i) {
// Try it. See if it gives us a more optimal solution
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
/*
dp[amount] has our answer. If we do not have an answer then dp[amount]
will be amount + 1 and hence dp[amount] > amount will be true. We then
return -1.
Otherwise, dp[amount] holds the answer
*/
return dp[amount] > amount ? -1 : dp[amount];
}
}