0322. 零钱兑换

[giscus[bot]]

0322. 零钱兑换

标签：广度优先搜索、数组、动态规划; 难度：中等; 题目链接 0322. 零钱兑换 - 力扣 (https://leetcode.cn/problems/coin-change/); 题目大意 描述：给定代表不同面额的硬币数组 $coins$ 和一个总金额 $amount$。 要求：求出凑成总金额所需的最少的硬币个数。如果无法凑出，则返回 $-1$。 ...

https://algo.itcharge.cn/Solutions/0300-0399/coin-change/

[Echo9573]

广度优先搜索的代码有问题
if cur == coin中不应该再加一步step
for coin in coins:
if cur == coin:
return step
elif cur > coin and cur - coin not in visited:
queue.append(cur - coin)
visited.add(cur - coin)