0322. 零钱兑换

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 的最短路径问题。我们可以用广度优先搜索的方法来做。

  1. 定义 visited 为标记已访问值的 set 集合变量,queue 为存放值的队列。

  2. amount 状态标记为访问,并将其加入队列 queue

  3. 令当前步数加 1,然后将当前队列中的所有值依次出队,并遍历硬币数组:

    1. 如果当前值等于当前硬币值,则说明当前硬币刚好能凑成当前值,则直接返回当前次数。
    2. 如果当前值大于当前硬币值,并且当前值减去当前硬币值的差值没有出现在已访问集合 visited 中,则将差值添加到队列和访问集合中。
  4. 重复执行第 3 步,直到队列为空。

  5. 如果队列为空,也未能减到 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)$。
本站总访问量  次  |  您是本站第  位访问者