322. 零钱兑换 · Algorithm Lab

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

示例 1：

输入： coins = [1, 2, 5], amount = 11输出： 3解释： 11 = 5 + 5 + 1

示例 2：

输入： coins = [2], amount = 3输出： -1

示例 3：

输入： coins = 1, amount = 0 输出： 0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

参考解法

下面保留的是原始练习仓库中的个人作答，可在右侧工作台中独立重写，再按需揭示对照。

python


class Solution(object):
    def coinChange(self, coins, amount):
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for i in range(amount + 1):
            for coin in coins:
                if i - coin < 0:
                    continue
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
        return -1 if dp[amount] == (amount + 1) else dp[amount]
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """