In this post, we are going to solve the 322. Coin Change problem of Leetcode. This problem 322. Coin Change is a Leetcode medium level problem. Let’s see the code, 322. Coin Change – Leetcode Solution.

Problem

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] <= 231 - 1
• 0 <= amount <= 104

Now, let’s see the code of 322. Coin Change – Leetcode Solution.

Coin Change – Leetcode Solution

We are going to provide you with the solution using both approaches:

• Memoization – Top-Down Approach
• Tabulation – Bottom-Up Approach

322. Coin Change – Solution in Java

This is the code of the Memoization or the Top-Down Approach for the problem coin change in Java Programming Language.

class Solution {
    
    public int solveMem(int[] coins, int amount, int[] dp){
        
        if(amount == 0){
            return 0;
        }
        
        if(amount < 0){
            return Integer.MAX_VALUE;
        }
        
        if(dp[amount] != -1){
            return dp[amount];
        }
        
        int min = Integer.MAX_VALUE;
        for(int e : coins){
            int ans = solveMem(coins,amount-e,dp);
            if(ans != Integer.MAX_VALUE)
                min = Math.min(ans+1,min);
           
        }
        dp[amount] = min;
        return min;
        
    }
    
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for(int i=0;i<=amount;i++) dp[i] = -1;
        int ans = solveMem(coins,amount,dp);
        if(ans == Integer.MAX_VALUE) return -1;
        else return ans;
    }
}

Now, let’s see the code of the Tabulation or the Bottom-Up Approach for the problem coin change in Java Programming Language.

class Solution {
    
    public int coinChange(int[] coins, int amount) {

        int ans = solveTab(coins,amount);
        return ans;
    }
    
    public int solveTab(int[] coins, int amount){
        int[] dp = new int[amount+1];
        for(int i=0;i<=amount;i++)dp[i] = Integer.MAX_VALUE;
        
        dp[0] = 0;
        for(int i = 1;i<=amount;i++)
        {
            for(int e : coins){
                if(i-e >= 0 && dp[i-e] != Integer.MAX_VALUE)
                dp[i] = Math.min(dp[i],1+dp[i-e]);
            }
        }
        if(dp[amount] == Integer.MAX_VALUE) return -1;
        else return dp[amount];
    }
}

322. Coin Change – Solution in C++

This is the code of the Memoization or the Top-Down Approach for the problem coin change in C++ Programming Language.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,-1);
        int ans = solveMem(coins,amount,dp);
        if(ans == INT_MAX) return -1;
        else return ans;
    }
    int solveMem(vector<int>& coins, int amount, vector<int>& dp){
        
        if(amount == 0){
            return 0;
        }
        
        if(amount < 0){
            return INT_MAX;
        }
        
        if(dp[amount] != -1){
            return dp[amount];
        }
        
        int mini = INT_MAX;
        for(int e : coins){
            int ans = solveMem(coins,amount-e,dp);
            if(ans != INT_MAX)
                mini = min(ans+1,mini);
           
        }
        dp[amount] = mini;
        return mini;
        
    }
};

Now, let’s see the code of the Tabulation or the Bottom-Up Approach for the problem coin change in C++ Programming Language.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int ans = solveTab(coins,amount);
        return ans;
    }
    int solveTab(vector<int>& coins, int amount){
        vector<int>dp(amount+1,INT_MAX);
        dp[0] = 0;
        for(int i = 1;i<=amount;i++)
        {
            for(int e : coins){
                if(i-e >= 0 && dp[i-e] != INT_MAX)
                dp[i] = min(dp[i],1+dp[i-e]);
            }
        }
        if(dp[amount] == INT_MAX) return -1;
        else return dp[amount];
    }
};

322. Coin Change – Solution in Python

Memoization or Top-Down Approach solution code in Python

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:            
        def coinChangeInner(rem, cache):
            if rem < 0:
                return math.inf
            if rem == 0:                    
                return 0       
            if rem in cache:
                return cache[rem]
            
            cache[rem] = min(coinChangeInner(rem-x, cache) + 1 for x in coins)                         
            return cache[rem]      
        
        ans = coinChangeInner(amount, {})
        return -1 if ans == math.inf else ans    

Tabulation or Bottom-Up Approach solution code in Python

class Solution:
    def coinChange(self, coins: 'List[int]', amount: 'int') -> 'int':
        dp = [0] + [float('inf') for i in range(amount)]
        for i in range(1, amount+1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i-coin] + 1)
        if dp[-1] == float('inf'):
            return -1
        return dp[-1]
        

Note: This problem 322. Coin Change is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.