0322：零钱兑换（★）

力扣第 322 题

题目

给你一个整数数组 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

相似问题：

• 0983：最低票价（1786 分）
• 2218：从栈中取出 K 个硬币的最大面值和（2157 分）
• 2224：转化时间需要的最少操作数（1295 分）
• 2547：拆分数组的最小代价（2019 分）
• 2902：和带限制的子多重集合的数目（2758 分）
• 2915：和为目标值的最长子序列的长度（1658 分）
• 2952：需要添加的硬币的最小数量（1784 分）
• 2979：最贵的无法购买的商品

分析

• 完全背包与 01 背包的区别在于递推式 f[i][j] 由 f[i][j-x] 而不是 f[i-1][j-x] 推出
• 可以将 dp 数组优化为一维，与 01 背包的区别仅在于 j 的遍历顺序不同

解答

1
2
3
4
5
6
7
8

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        f = [0]+[inf]*amount
        for x in coins:
            for j in range(x,amount+1):
                f[j] = min(f[j],1+f[j-x])
        return f[-1] if f[-1]<inf else -1

744 ms