322. Coin Change

Problem Statement

link: LeetCode.cn LeetCode

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example:

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

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

Input: coins = [1], amount = 0 Output: 0

Solution Approach

The solution utilizes dynamic programming to iteratively compute the minimum number of coins needed to reach each amount from 0 to the target amount, selecting the optimal coin denomination at each step.

Algorithm

1. Dynamic Programming: Employs dynamic programming to compute the minimum number of coins needed for each amount from 0 to the target amount.

2. Coin Selection: Iterates through each amount, considering all available coin denominations to calculate the minimum number of coins required for that amount.

3. Minimum Coin Count: Updates the DP table with the minimum number of coins needed for each amount. Returns the result from the last element of the DP table or -1 if the target amount cannot be achieved.

Implement

    class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
      coins.sort()
      dp = [0] + [float('inf')] * amount
      for i in range(1, amount + 1):
        for c in coints:
          if i >= c:
            dp[i] = min(dp[i], dp[i - c] + 1)
      return dp[-1] if dp[-1] != float('inf') else -1
    
       

    
    

Twitter  facebook  Email