Minimum coin change class giving wrong answer

Question

Trying to [solve] the problem in leetcode (322):

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.

I am stuck in this input: coins = [2] and target = 3

I wonder why it is returning 0? I debugged this but not able to figure out.

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        def get_cost(coins, amount):
            if amount == 0:
                return 0
            min_cost = float('inf')
            for coin in coins:
                if amount >= coin:
                    min_cost = min(min_cost, 1 + self.coinChange(coins, amount - coin))
            return min_cost

        cost = get_cost(coins, amount)
        if cost == float('inf'):
            return -1
        return cost

Tag all change-making questions coin-change. That way you can find related questions. — smci
@AnupamGhosh: Try it here leetcode.com/problems/coin-change/description — noman pouigt

perreal perreal · Accepted Answer · 2018-02-11T06:08:12

Your logic is not correct, you want to do something like this: the minimum cost either contains the current coin or it does not. This would in pseudo code look like:

min_coins = current cost + min(cost without using this coin, cost using this coin)

so you should put the current cost in your state and also keep track of which coins you are allowed to use.

Minimum coin change class giving wrong answer

1 Answers