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:广度优先搜索 #
我们可以从 amount
开始,每次从 coins
的硬币中选中 1
枚硬币,并记录当前挑选硬币的次数。则最快减到 0
的次数就是凑成总金额所需的最少的硬币个数。这道题就变成了从 amount
减到 0
的最短路径问题。我们可以用广度优先搜索的方法来做。
-
定义
visited
为标记已访问值的 set 集合变量,queue
为存放值的队列。 -
将
amount
状态标记为访问,并将其加入队列queue
。 -
令当前步数加
1
,然后将当前队列中的所有值依次出队,并遍历硬币数组:- 如果当前值等于当前硬币值,则说明当前硬币刚好能凑成当前值,则直接返回当前次数。
- 如果当前值大于当前硬币值,并且当前值减去当前硬币值的差值没有出现在已访问集合
visited
中,则将差值添加到队列和访问集合中。
-
重复执行第 3 步,直到队列为空。
-
如果队列为空,也未能减到
0
,则返回-1
。
思路 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:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(amount \times size)$。其中 $amount$ 表示总金额,$size$ 表示硬币的种类数。
- 空间复杂度:$O(amount)$。