Leetcode Coin Change problem solution

YASH PAL,

In this Leetcode Coin Change problem solution, You are given an integer array of 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.

Leetcode Coin Change problem solution

Problem solution in Python.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0 or coins is None or len(coins) == 0:
            return 0
        dp = [0] * (amount + 1)
        for coin in coins:
            for i in range(coin, amount + 1):
                if i == coin:
                    dp[i] = 1
                elif dp[i] == 0 and dp[i - coin] != 0:
                    dp[i] = dp[i - coin] + 1
                elif dp[i - coin] != 0:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
                    
        return -1 if dp[amount] == 0 else dp[amount]

Problem solution in Java.

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                if (dp[j - coin] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - coin] + 1);
                }
            }
        }
        
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

Problem solution in C++.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> DP(amount+1, INT_MAX-1);
        int n = coins.size(), i, j;
        DP[0] = 0;
        for(i=1; i<=amount; i++)
        {
            for(j=0; j<n; j++)
            {
                if(i-coins[j]>=0)
                    DP[i] = min(DP[i], DP[i-coins[j]]+1);
            }
        }
        
        if(DP[amount] == INT_MAX-1)
            return -1;
        else
            return DP[amount];
    }
};

Problem solution in C.

int coinChange(int* coins, int coinsSize, int amount) {
    unsigned int* dp = (unsigned int*)malloc(sizeof(int)*(amount + 1));
    int i, j, ans, t;
    memset(dp, 0xff, sizeof(int) * (amount + 1));
    dp[0] = 0;
    for (i = 1; i <= amount; i++) {
        for (j = 0; j < coinsSize; j++) {
            if (coins[j] <= i) {
                t = dp[i - coins[j]] + 1;
                if (t > 0 && t < dp[i]) {
                    dp[i] = t;
                }
            }      
        }
    }
    ans = dp[amount];
    free(dp);
    return ans;
}

coding problems solutions