Change II (Question No. 518)

The title

Give coins of different denominations and a total amount. Write the function to calculate the number of coin combinations that add up to the total amount. Suppose there are an infinite number of coins of each denomination.

Example 1:

Input: Amount =5, Coins = [1, 2, 5] Output: 4 Explanation: There are four ways to raise the total amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1Copy the code

Example 2:

Input: Amount = 3, Coins = [2] Input: Amount = 3, Coins = [2] Output: 0Copy the code

Example 3:

Input: Amount = 10, Coins = [10Copy the code

Note:

You can assume:

  • 0 <= amount <= 5000
  • 1 <= coin (coin value) <= 5000
  • Coins of no more than500 种
  • The results conform to the32Bit signed integer

link

Leetcode-cn.com/problems/co…

explain

I did my best. I didn’t think of a solution to this problem.

The recursion that I came up with at the beginning, is similar to the recursion that I had in the last problem, so I can modify it a little bit, but I’m going to end up with a timeout.

Then began to recursion on the complement, and finally did not fill out, really can not GET the number of coin combination of the relationship, can not find the relationship to find the recursive equation, of course GG.

But the awkward question came, finally even looked at the answer is also a little understanding, took a long time to understand a little, and a bit confused.

The overall logic is as follows:

  1. Assuming input: Amount = 5, Coins = [1, 2, 5], if you use the amount + 1 DP array recursion, the following features must be met:

    • If you recurse with an array dp of length amount + 1.
    • Each index represents a recursive amount.
    • Each element is the number of coin combinations.
    • The 0 position is the initial state, and if set to 1, the recursion starts with 1 number of combinations.

  2. We can split it by coin and recurse the result:

    • Coin 1: [1,1,1,1,1,1]
    • Coin 2: [1,0,1,0,1,0]
    • Coin 5: [1,0,0,0,0,1]
    • Coin 1,2: [1,1,2,2,3,3]
    • Coins 1,2, 5: [1,1,2,2,3,4]

  3. The recursion method is as follows:

    • Calculate the face value of each coin in turncoinThe recursive result of.
    • The current amount I is fromi - coinaddedcoinAnd come.
    • Current number of new coin combinationsdp[i]Is equal to the number of combinations that the previous coin recurses to Idp[i], plusi - coinThe combination of severaldp[i - coin]And come.
    • The state transition equation is:dp[i] = dp[i] + dp[i - coin].

Brother said very clearly, the author said more is nonsense, 👇 look at the code:

Your own answer (recursion)

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

The classical recursion, similar to the last problem, runs to the 17th use case timeout GG.

Better approach (Dynamic programming: Two-dimensional arrays)

var change = function(amount, coins) {
  if (amount === 0) return 1;
  const dp = [Array(amount + 1).fill(1)];
  for (let i = 1; i < amount + 1; i++) {
    dp[i] = Array(coins.length + 1).fill(0);
    for (let j = 1; j < coins.length + 1; j++) {
      if (i - coins[j - 1] >= 0) {
        dp[i][j] = dp[i][j - 1] + dp[i - coins[j - 1]][j];
      } else {
        dp[i][j] = dp[i][j - 1];
      }
    }
  }
  return dp[dp.length - 1][coins.length];
}
Copy the code

The classical two-dimensional array DP, DP [I] is the current amount, and DP [j] is the combined number of coins of the current denomination.

Of course, dimension reduction is also possible for classic DP 👇 :

Better approach (Dynamic programming: Dimension reduction)

var change = function(amount, coins) {
  if (amount === 0) return 1;
  var dp = new Array(amount + 1).fill(0)
  dp[0] = 1
  for (const coin of coins) {
    for (let i = 1; i < amount + 1; i++) {
      if (coin <= i) {
        dp[i] = dp[i] + dp[i - coin]
      }      
    }
  }
  return dp[amount]
};
Copy the code

It may be a little confusing, but I put the coin loop on the outside and the amount loop on the inside.

This is understandable to get the order of the data, if the coin cycle is outside, then the inside of the loop will layer by layer to get all the coin combination data; If the coin cycle is inside, then only the current number of the coin combination will be available, and the subsequent numbers will not be available.

summary

This piece of dynamic programming is said to be simple, the author directly autistic, brush the problem is sometimes like this, sometimes can not think of that point has been unable to think of the answer, think of that point the answer will come out, but also have to continue to practice!

Originally thought that change is the skill of Chinese people, after reading these two questions I feel that I really can not change…




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ