catalogue

# 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