DP - Coin Change

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.

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: "11" can be made up of using least number of coins 5 + 5 + 1.

Input: coins = [2], amount = 3
Output: -1
Explanation: "3" cannot be made up of using given coins.

Input: coins = [1], amount = 0
Output: 0
Explanation: There are 0 ways to make up amount 0.

Solution 1 - using brute force approach
Solution 2 - using DP memoization
Solution 3 - using DP Bottom-Up approach using tabulation and memory optimization

In this approach, we will generate all possible ways to to come up with the amount using the combinations from coins array. For every number at index i from coins array, we compute remainder = amount-coins[i] and for this remainder repeat the same process recursively until the remainder becomes 0.

If the remainder becomes 0 that means we have found a way to come up with the amount using numbers from coins array and if the remainder becomes negative, that means there is no possibility.

For example, consider if the coins = [1, 1, 2], and amount = 3. When we try all different combinations using the numbers from array, the decision tree looks like below diagram. From every node, we are trying with all possibilities using coins array elements.

coins change brute force approach decision tree

We will create a function bruteForceApproach that takes inputs coins array and amount and returns min as answer.
Base cases are:
- If the input amount is 0, then we will return 0.
- If the input amount is less than 0, then we will return -1 as a way to indicate that we cannot make up amount using the coins given.
Then, for every number in coins array compute the remainder using amount - coins[i], and call bruteForceApproach function recursively with coins array and remainder. Repeat this process until one of the one of the base case is hit. i.e. remainder will become 0 if we can make up amount or remainder will become less than 0 if the amount cannot be made using coins.
While calling the bruteForceApproach function recursively, if a path found to make up the sum, that is return value of the function will be greater than or equal to 0, then increment the count of coins and keep track of min variable.

public class CoinChange { /* Brute force approach */ static int bruteForceApproach(int[] coins, int amount) { if (amount == 0) { return 0; } if (amount <0){ return -1; } int min = -1; for(int i=0; i<coins.length; i++) { int remainder = amount-coins[i]; int count = bruteForceApproach(coins, remainder); if(count >=0) { count++; if(min == -1 || count <min){ min = count; } } } return min; } }

Complexity Analysis:

Time complexity: Above code runs in O(2^{t + n}) time where n is the length of coins array and t is the amount value, this is because we are generating a decision tree with possible sub problems by taking possibilities with each number from coins array and depth can go as big as amount.
Space complexity: O(t + n) since we calling the function recursively, this is the stack memory.

From the above brute force approach, we can notice that there are some overlapping problems, such as sub problems highlighted in the below diagram, likewise there are many other overlapping sub problems.

In this approach, we are going to cache the results in a HashMap with key as amount and value as min, that is minimum number of coins needed to make up that amount.

import java.util.HashMap; public class CoinChange { /* DP memoization */ static int dpMemoization(int[] coins, int amount) { HashMap<Integer, Integer> cache = new HashMap<>(); return dpMemoizationRec(coins, amount, cache); } static int dpMemoizationRec(int[] coins, int amount, HashMap<Integer, Integer> cache) { if (amount == 0) { return 0; } if (amount <0){ return -1; } if(cache.containsKey(amount)) { return cache.get(amount); } int min = -1; for(int i=0; i<coins.length; i++) { int remainder = amount-coins[i]; int count = bruteForceApproach(coins, remainder); if(count >=0) { count++; if(min == -1 || count <min){ min = count; } } } cache.put(amount, min); return min; } }

Complexity Analysis:

Time complexity: Above code runs in O(t * n) time where n is the length of coins array and t is the amount value. This is because we are looping for all coins from the array and amount number of times by taking remainder using each coin.
Space complexity: O(t * n) for the stack used in recursive calls and the cache that we are maintaining.

In this approach we will look at solving the problem using Dynamic programming using tabulation caching mechanism.
The time and memory complexity will be same as above solution using memoization, but we can optimize memory in this approach.

In this solution, we are going to create a temporary array to cache minimum number of coins needed to make up amount for every number from 0......amount and finally return last indexed value if there is a possibility to make up the amount.

We are going to initialize cache[0] = 0, that is to make up amount 0 we need 0 coins and initialize other indexes with amount + 1 as a way to indicate whether we can make up that amount or not. int[] cache = new int[amount +1]; // +1 to include 0 amount as well. cache[0] = 0; Arrays.fill(cache, 1, amount+1, amount+1); // here, we are passing array to be filled, starting index, // end index (exclusive) and value to be filled
When we are at index i (here i represents an amount), we check how many coins needed to come up with that amount:
- For every coin from the coins array, check if the remainder amount i - coin is greater than equal to 0, meaning that it is a considerable coin to make up the index i amount.
- Update the cache with MIN (cache[i], 1 + cache[i-coin]), here we are checking 1 + cache[i-coin] to check if the remainder amount i-coin already present in cache and if that is minimum, we take that. cache[i] = Math.min(cache[i], 1 + cache[i-coin]);
Finally, if the value at amount index in cache array is not amount +1 (what it is initialized with), then simply return that, otherwise return -1 to indicate that amount cannot be made up using coins.

Consider an example with coins = [1, 1, 2] and amount = 3 DP tabulation example

In the first step we will initialize cache array with cache = [0, 4, 4, 4].
When i == 1, that is for amount 1:
- Check if we can consider 1^st coin 1, remainder will be 0, so we can consider it. Now update the cache. cache[1] = MIN (4, 1 + cache[remainder]) = MIN (4, 1 + cache[0]) = MIN(4, 1 + 0) = 1;
- Check if we can consider 2^nd coin 1, remainder will be 0, so we can consider it. Now update the cache. cache[1] = MIN (1, 1 + cache[remainder]) = MIN (1, 1 + cache[0]) = MIN(1, 1 + 0) = 1;
- Check if we can consider 3^rd coin 2, remainder will be -1, so we cannot consider this coin as this coin is greater than amount 1.
When i == 2, that is for amount 2:
- Check if we can consider 1^st coin 1, remainder will be 1, so we can consider it. Now update the cache. cache[2] = MIN (4, 1 + cache[remainder]) = MIN (4, 1 + cache[1]) = MIN(4, 1 + 1) = 2;
- Check if we can consider 2^nd coin 1, remainder will be 1, so we can consider it. Now update the cache. cache[2] = MIN (2, 1 + cache[remainder]) = MIN (2, 1 + cache[1]) = MIN(2, 1 + 1) = 2;
- Check if we can consider 3^rd coin 2, remainder will be 0, so we can consider it. Now update the cache. cache[2] = MIN (2, 1 + cache[remainder]) = MIN (2, 1 + cache[0]) = MIN(2, 1 + 0) = 1;
When i == 3, that is for amount 3:
- Check if we can consider 1^st coin 1, remainder will be 2, so we can consider it. Now update the cache. cache[2] = MIN (4, 1 + cache[remainder]) = MIN (4, 1 + cache[2]) = MIN(4, 1 + 1) = 2;
- Check if we can consider 2^nd coin 1, remainder will be 1, so we can consider it. Now update the cache. cache[2] = MIN (2, 1 + cache[remainder]) = MIN (2, 1 + cache[1]) = MIN(2, 1 + 1) = 2;
- Check if we can consider 3^rd coin 2, remainder will be 1, so we can consider it. Now update the cache. cache[2] = MIN (2, 1 + cache[remainder]) = MIN (2, 1 + cache[1]) = MIN(2, 1 + 1) = 2;
Finally, check if cache[amount], this value is update that what it is initialized with, so simply rturn that. So, our answer is 2.

import java.util.Arrays; public class CoinChange { /* DP tabulation bottom-up approach */ static int dpTabulation(int[] coins, int amount) { int[] cache = new int[amount + 1]; cache[0] = 0; Arrays.fill(cache, 1, amount+1, amount+1); // fill the cache with amount +1 // reason why we are using amount+1 as a way to indicate // whether we can make up the amount using coins not for(int i=1; i<cache.length; i++) { for(int coin : coins) { if(i-coin >=0) { cache[i] = Math.min(cache[i], 1+ cache[i-coin]); } } } if(cache[amount] != amount+1) { // meaning that amount indexed element in cache // has different value than amount+1, what it is initialized with return cache[amount]; } return -1; } }

Complexity Analysis:

Time complexity: Above code runs in O(t * n) time where n is the length of coins array and t is the amount value. This is because we are looping for all coins from the array and amount number of times by taking remainder using each coin.
Space complexity: O(t) where t is the input amount since the cache is initialized with amount size.

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis:

Complexity Analysis:

Complexity Analysis: