最小硬币兑换等级给出错误答案

Question

尝试[解决]leetcode（322）中的问题：

你会得到不同面额的硬币和总金额。写一个函数来计算你需要的最少数量的硬币来组成这个数量。如果这些硬币的任何组合都不能弥补这个金额，返回-1。

我被困在这个输入：硬币=[2]和目标=3

我想知道它为什么返回0？我调试了这个，但没能弄清楚。

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

Answer 1

你的逻辑不正确，你想做这样的事情：最小成本要么包含当前硬币，要么不包含。这在伪代码中看起来像：

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

因此，你应该把当前的成本放在你所在的州，并记录你可以使用哪些硬币。