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/

Related Posts