catalogue

1. Title Description

2. Problem solving analysis

3. Code implementation

1. Title Description

Give you an integer array of coins to represent coins of different denominations; And an integer amount, representing the total amount.
Calculate and return the minimum number of coins required to make up the total amount. If no combination of coins can make up the total amount, return - 1. You can think that the number of coins of each kind is unlimited.

Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:
Input: coins = [2], amount = 3
Output: - 1

Example 3:
Input: coins = [1], amount = 0
Output: 0
 
Tips:
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

Source: LeetCode
Link: https://leetcode-cn.com/problems/coin-change
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.

2. Problem solving analysis

The minimum number of coins -- > the shortest path can be solved by breadth first search.                

The amount (to be exchanged) is represented by the status of the node. The starting node value is total amount. Each (directed) edge represents the selected coin. After passing through the edge, the value of the adjacent node is equal to the value of the previous node minus the coin value represented by edge. Since the number of each coin is unlimited, all candidate coins can be considered when traversing its adjacent nodes from each "node". So... Search in a breadth first manner until you find the first node with a value of 0.

3. Code implementation

import sys
import time
import random
from   collections import deque
from   typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        assert(amount >= 0)
        if amount == 0:
            return 0
        if amount < min(coins):
            return -1

        q = deque([amount])
        visited = set()
        layer = 1
        while q:            
            # print('layer = {0}, q.len = {1}'.format(layer,len(q)))
            n = len(q)
            for _ in range(n): # Traverse the current layer
                a = q.pop()
                if a in coins:
                    return layer
                # Add a's neighbours into q
                for c in coins:
                    b = a - c
                    if b > 0 and b not in visited:
                        visited.add(b)                        
                        q.appendleft(b)               
            layer = layer + 1
        return -1

if __name__ == '__main__':

    import time
    sln   = Solution()

    # testcase1
    coins = [1, 2, 5] 
    amount = 11
    print(sln.coinChange(coins, amount))

    # testcase2
    coins = [2] 
    amount = 3
    print(sln.coinChange(coins, amount))

    # testcase3
    coins = [1, 2, 5, 10, 20,50, 100] 
    amount = 1001
    tStart= time.time()
    print(sln.coinChange(coins, amount))
    tElapsed = time.time() - tStart        
    print('tElapsed = ', tElapsed, ' (sec)')

    # testcase3
    coins = [470,35,120,81,121]
    amount = 9825
    tStart= time.time()
    print(sln.coinChange(coins, amount))
    tElapsed = time.time() - tStart        
    print('tElapsed = ', tElapsed, ' (sec)')

Execution time: 424 ms, beating 99.17% of users in all # Python 3 # submissions

Memory consumption: 15.9 MB, beating 18.33% of users in all # Python 3 # submissions

Pass test case: 188 / 188

This problem can also be solved by dynamic programming.

Back to the general catalogue of this note series: Leetcode problem solving notes of slow ploughing of stupid cattle (dynamic update...)https://chenxiaoyuan.blog.csdn.net/article/details/123040889