python - 给出错误答案的最小硬币变化类

Question

试图[解决] 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.

我被困在这个输入中:coins = [2] and target = 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)

所以你应该把当前的成本放在你的状态中，并记录你被允许使用的硬币。