I. Title Description:

Leetcode322: change

Give coins of different denominations and an amount. Write a function to calculate the minimum number of coins needed to make up the total. If no one coin combination makes up the total, return -1. You can think of an infinite number of each coin.

Example 1:

Input: Coins = [1, 2, 5], amount = 11Copy the code

Example 2:

Input: Coins = [2], amount = 3 Output: -1Copy the code

Example 3:

Input: Coins = [1], amount = 0 Output: 0Copy the code

Example 4:

Input: Coins = [1], amount = 1 Output: 1Copy the code

Example 5:

Input: Coins = [1], amount = 2 Output: 2Copy the code

Ii. Analysis of Ideas:

Solution 1: Greedy algorithm

In order to make up the total amount, we must choose the largest denomination coins first. Therefore, greedy algorithm can be used to solve the problem.

  1. Coins are arranged in descending order, from 0 to the length of the array
  2. Round = The maximum number of coins of the current denomination available
  3. Amount = 0, end of one exchange, update the minimum amount of exchange
  4. Pruning: Record the number of exchanges. The number of subsequent exchanges cannot be greater than the minimum number of exchanges

Solution 2: Dynamic programming

The problem can also be solved by bottom-up dynamic programming. Given coins of different denominations [1, 2, 5] and the target is 120, what is the minimum number of coins required?

  • We want to decompose the sub-problem, hierarchical level to find the optimal sub-structure, see this again to dizzy ha, suffocating ~~ below immediately for example.

  • Here we use top-down thinking to think about the problem, and then use a bottom-up approach to solve the problem, to experience the algorithm of fire and ice.

  • Dp [I]: indicates the number of coins in the optimal solution when the total amount is I

  • Let’s think about it: how many ways are there to get the total amount of 120? The following idea is key!! There are 3 ways, because we have 3 different denominations of coins.

    1. Take a coin with a face value of 1 + the number of coins with the best solution of 119. We’re just going to assume that the number of coins for the optimal solution is 119 and somebody already figured it out for us, so we don’t have to worry about that. Namely, dp[119] + 1
    2. Take a coin of value 2 + the number of coins for the best solution of total value 118. Here we just assume that the number of coins in the optimal solution for the total amount of 118 has already been calculated for us, that is, dp[118] + 1
    3. Take a coin of value 5 + the number of coins for the best solution of 115. Here we just assume that the number of coins in the optimal solution for the total amount of 115 was already calculated for us, that is, dp[115] + 1

  • Therefore, the optimal solution with a total amount of 120 is the optimal one of the above three solutions, that is, the one with the least number of coins. We will use the code to express it next:

  • dp[120] = Math.min(dp[120], dp[119] + 1, dp[118] + 1, dp[115] + 1);

  • Min (dp[n], dp[n-coin] + 1) where coin is the denominational value of a coin. Coin is the value of a coin.

Iii. AC Code:

Greedy algorithm code

var coinChange = function(coins, amount, res = Infinity) {
    coins.sort((a, b) => b - a)
    var d = (amount, index, count) => {
        if (amount === 0) return res = Math.min(res, count)
        if (index === coins.length) return
        for (var n = amount / coins[index] | 0; count + n < res && n >= 0; n--) 
            d(amount - n * coins[index], index + 1, count + n)
    }
    return d(amount, 0, 0), res === Infinity ? -1 : res
};
Copy the code

Dynamic programming code

var coinChange = function(coins, amount, dp = [0].concat(Array(amount).fill(amount + 1))) {
  for (var i = 1; i <= amount; i++)
      for (coin of coins)
          if (i >= coin) dp[i] = Math.min(dp[i], dp[i - coin] + 1)
  return dp[amount] > amount ? -1 : dp[amount]
};
Copy the code

Iv. Summary:

By doing change for this problem, I first reviewed the dynamic programming I studied last week, and then I learned the idea of greedy algorithm. Greedy algorithms are suitable for: always make the best choice at the moment when solving a problem. The small change problem is to choose the largest value of coins to match first, so greedy algorithm can be used to solve.

This article is participating in the “Gold Digging march Campaign”, click to see the details of the campaign