My first solution is using dynamic programming. Then I want to also try breath-first-search. The first version of my BFS:

class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount == 0:
return 0
# bfs
depth, ans = 1, -1
queue = [amount]
while len(queue) > 0:
new_queue = []
for node in queue:
for coin in coins:
if coin > node:
continue
if coin == node:
return depth
else:
new_queue.append(node-coin)
queue = new_queue
depth += 1
return ans

It could get the correct answer but met TLE (Time Limit Exceeded) error when running the below case:

[2,3,5,7,11,13,17,19,21]
9999

After checking the variables “queue” and “new_queue”, I noticed there are many duplicate values. Therefore I set them to “set” instead of “list”:

class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount == 0:
return 0
# bfs
depth, ans = 1, -1
queue = {amount}
while len(queue) > 0:
new_queue = set()
for node in queue:
for coin in coins:
if coin > node:
continue
if coin == node:
return depth
else:
new_queue.add(node-coin)
queue = new_queue
depth += 1
return ans

It’s faster but still costs about 5 seconds (This is too long for a contest in LeetCode).

Actually, there are still many duplicated values. Not in one “queue”, but in different depths. Let me take this case:

`Input: coins = [1,2,5], amount = 11`

as an example. The BFS of it looks like this:

The program already starts to check “9” at the second layer, so it’s just a waste of time to check “9” again in the third layer. Thus, we can ignore any number in “new_queue” that is already in all the previous “queues”.

I will add a new set called “already” to record all the values the program ALREADY TO PROCESS, and minus it before searching the next depth. The new code only costs 90ms:

class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount == 0:
return 0
# bfs
depth, ans = 1, -1
queue = {amount}
already = set()
while len(queue) > 0:
new_queue = set()
for node in queue:
for coin in coins:
if coin > node:
continue
if coin == node:
return depth
else:
new_queue.add(node-coin)
already |= queue
queue = new_queue - already
depth += 1
return ans

———- 2023.01.24 ———-

Seems other BFS problems could also borrow this idea. Like this one I made https://leetcode.com/submissions/detail/884138668/