0322. 零钱兑换 #

标签：动态规划
难度：中等

题目大意 #

描述：给定代表不同面额的硬币数组 coins 和一个总金额 amount。

要求：求出凑成总金额所需的最少的硬币个数。如果无法凑出，则返回 -1。

说明：

$1 \le coins.length \le 12$。
$1 \le coins[i] \le 2^{31} - 1$。
$0 \le amount \le 10^4$。

示例：

1
2
3
4
5
6
7


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


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

解题思路 #

思路 1：广度优先搜索 #

我们可以从 amount 开始，每次从 coins 的硬币中选中 1 枚硬币，并记录当前挑选硬币的次数。则最快减到 0 的次数就是凑成总金额所需的最少的硬币个数。这道题就变成了从 amount 减到 0 的最短路径问题。我们可以用广度优先搜索的方法来做。

定义 visited 为标记已访问值的 set 集合变量，queue 为存放值的队列。
将amount 状态标记为访问，并将其加入队列 queue。
令当前步数加 1，然后将当前队列中的所有值依次出队，并遍历硬币数组：
1. 如果当前值等于当前硬币值，则说明当前硬币刚好能凑成当前值，则直接返回当前次数。
2. 如果当前值大于当前硬币值，并且当前值减去当前硬币值的差值没有出现在已访问集合 visited 中，则将差值添加到队列和访问集合中。
重复执行第 3 步，直到队列为空。
如果队列为空，也未能减到 0，则返回 -1。

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        
        visited = set([amount])
        queue = collections.deque([amount])

        step = 0
        while queue:
            step += 1
            size = len(queue)
            for _ in range(size):
                cur = queue.popleft()
                for coin in coins:
                    if cur == coin:
                        step += 1
                        return step
                    elif cur > coin and cur - coin not in visited:
                        queue.append(cur - coin)
                        visited.add(cur - coin)
            
        return -1

思路 1：复杂度分析 #

时间复杂度：$O(amount \times size)$。其中 $amount$ 表示总金额，$size$ 表示硬币的种类数。
空间复杂度：$O(amount)$。

思路 2：完全背包问题 #

可以转换为有 n 枚不同的硬币，每种硬币可以无限次使用。凑成总金额为 amount 的背包，最少需要多少硬币。

1. 划分阶段 #

按照子串的起始位置进行阶段划分。

2. 定义状态 #

定义状态 dp[i] 表示为：凑成总金额为 i 的最少硬币数量。

3. 状态转移方程 #

dp[i] 来源于两部分：

不使用当前硬币，只使用之前硬币凑成金额 i 的最少硬币数量。
凑成金额 i - num 的最少硬币数量，再加上当前硬币。

上述两者的较小值即为 dp[i]。

4. 初始条件 #

凑成总金额为 0 的最少硬币数量为 0，即 dp[0] = 0。

5. 最终结果 #

根据我们之前定义的状态，dp[i] 表示为：凑成总金额为 i 的最少硬币数量。则最终结果为 dp[amount]。

思路 2：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf') for _ in range(amount + 1)]
        dp[0] = 0

        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)

        if dp[amount] != float('inf'):
            return dp[amount]
        else:
            return -1

思路 2：复杂度分析 #

时间复杂度：$O(amount \times size)$。其中 $amount$ 表示总金额，$size$ 表示硬币的种类数。
空间复杂度：$O(amount)$。