目录

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

相似问题:

分析

  • 完全背包与 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