题目描述

[EN | CN]

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

示例 1:

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

示例 2:

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

说明:

你可以认为每种硬币的数量是无限的。

解法 1:背包DP

为了练习背包问题,所以这个解法是用动态规划,实际上用别的方法要更合适。

动规三部曲:

第一步找记忆。要记住的是是当总金额为 $j$ 时我们凑成该总金额所需要的最少的硬币个数。

第二步找递推关系式。当我们考虑到总金额 $j$ 时,所需的最少硬币个数为: $$ M_j = \min\{ M_{j-\text{coins}[i]} + 1 ~|~ i \in [0, n) \} $$ 第三步找初试值。初始化 $M$ 使得 $M_0=0$,表示此取法合法;其他元素都为 INF,表示此条件不满足,基于此条件的都不满足。

假设硬币种类为 $n$,目标金额为 $c$,那么

  • 时间复杂度为 $O(n \cdot c)$;
  • 空间复杂度为 $O(c)$。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0

        n = len(coins)
        INF = float('inf')

        m = [0] + [INF for _ in range(amount)]
        for j in range(1, amount + 1):
            m[j] = min([
                m[j - coins[i]] + 1
                if j - coins[i] >= 0 else INF
                for i in range(n)
            ])

        return m[amount] if m[amount] != INF else -1
  • 执行用时:1524 ms,在所有 Python3 提交中击败了 69.53% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 13.67% 的用户。
▲