You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.

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

Note:
You may assume that you have an infinite number of each kind of coin.

[code lang="java"]
class Solution {
    public int coinChange(int[] coins, int amount) {
        
    }
}
[code]

Idea – 1

Starting with the first coin we try taking it once, twice etc., for each such choice we try taking second coin once, twice, etc. If the smallest coin goes into amount m number of times and there are n coins, time complexity is O(n^m) and space complexity due to recursion stack is O(n). 
[code lang="java"]
class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = dfs(coins, 0, amount);
        
        return n == Integer.MAX_VALUE ? -1 : n;
    }
    
    private int dfs(int[] coins, int i, int amount)
    {
        if(i >= coins.length || amount < 0)
        {
            return Integer.MAX_VALUE;
        }
        
        if(amount == 0) // found a change
        {
            return 0;
        }
        
        int takeit = dfs(coins, i, amount-coins[i]);
        if(takeit < Integer.MAX_VALUE)
        {
            // take into account the current coin
            ++takeit;
        }
        
        int leaveit = dfs(coins, i+1, amount);
        
        return Math.min(takeit, leaveit);
    }
}
[code]

Time limit exceeded for the following input:

[122,112,383,404,25,368]
6977

Idea – 2

Looking at dfs(), it has two params of interest i and amount, so there are only n*amount number of distinct calls. We shall cache. Time complexity is O(n\cdot \textrm{amount}) and space complexity is also O(n\cdot \textrm{amount}). 
[code lang="java"]
class Solution {
    public int coinChange(int[] coins, int amount) {
        
        if(coins.length == 0)
        {
            return -1;
        }
        
        Integer[][] cache = new Integer[coins.length][amount+1];
        
        int n = dfs(coins, 0, amount, cache);
        
        return n == Integer.MAX_VALUE ? -1 : n;
    }
    
    private int dfs(int[] coins, int i, int amount, Integer[][] cache)
    {
        if(i >= coins.length || amount < 0)
        {
            return Integer.MAX_VALUE;
        }
        
        if(amount == 0) // found a change
        {
            return 0;
        }
        
        if(cache[i][amount] != null)
        {
            return cache[i][amount];
        }
        
        int takeit = dfs(coins, i, amount-coins[i], cache);
        if(takeit < Integer.MAX_VALUE)
        {
            // take into account the current coin
            ++takeit;
        }
        
        int leaveit = dfs(coins, i+1, amount, cache);
        
        cache[i][amount] = Math.min(takeit, leaveit);
        
        return cache[i][amount];
    }
}
[code]

Runtime: 41 ms, faster than 12.06% of Java online submissions for Coin Change.
Memory Usage: 38.3 MB, less than 10.49% of Java online submissions for Coin Change.

Idea – 3

Bottom up dynamic programming, time and space O(n\cdot \textrm{amount}). 
[code lang="java"]
class Solution {
    public int coinChange(int[] coins, int amount) {
        
        if(coins.length == 0)
        {
            return -1;
        }
        
        int n = coins.length;
        
        int[][] dp = new int[n][amount+1];
        for(int a = 1; a <= amount; ++a)
        {
            dp[0][a] = (a%coins[0]==0) ? a/coins[0] : Integer.MAX_VALUE;
        }
        
        for(int i = 0; i < n; ++i)
        {
            dp[i][0] = 0;
        }
        
        for(int i = 1; i < n; ++i)
        {
            for(int a = 1; a <= amount; ++a)
            {
                // if taking current coin makes sense
                int takeit = (coins[i] <= a && dp[i][a-coins[i]] != Integer.MAX_VALUE) ? 1+dp[i][a-coins[i]] : Integer.MAX_VALUE;
                int leaveit = dp[i-1][a];
                
                dp[i][a] = Math.min(takeit, leaveit);
            }
        }
        
        return dp[n-1][amount] == Integer.MAX_VALUE ? -1 : dp[n-1][amount];
    }
}
[code]

Runtime: 13 ms, faster than 78.26% of Java online submissions for Coin Change.
Memory Usage: 37.5 MB, less than 90.66% of Java online submissions for Coin Change.

Idea – 4

To update dp[i][a], we need either dp[i-1][a] or dp[i][a-coins[i]], so keeping a single row is enough. Thus time remains O(n\cdot \textrm{amount}), but space becomes O(\textrm{amount}). 
[code lang="java"]
class Solution {
    public int coinChange(int[] coins, int amount) {
        
        if(coins.length == 0)
        {
            return -1;
        }
        
        int n = coins.length;
        
        int[] dp = new int[amount+1];
        
        // 0-th coin
        for(int a = 1; a <= amount; ++a)
        {
            dp[a] = (a%coins[0]==0) ? a/coins[0] : Integer.MAX_VALUE;
        }
        
        for(int i = 1; i < n; ++i)
        {
            for(int a = 1; a <= amount; ++a)
            {
                // if taking current coin makes sense
                int takeit = (coins[i] <= a && dp[a-coins[i]] != Integer.MAX_VALUE) ? 1+dp[a-coins[i]] : Integer.MAX_VALUE;
                int leaveit = dp[a];
                
                dp[a] = Math.min(takeit, leaveit);
            }
        }
        
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}
[code]

Runtime: 11 ms, faster than 84.75% of Java online submissions for Coin Change.
Memory Usage: 37 MB, less than 93.91% of Java online submissions for Coin Change.

Leave a comment