518. Change for II

Answer:

  1. Assume that amount = 5, Coins = [1, 2, 5] is entered. If the dp array with length of amount + 1 is used for recursion, the following characteristics must be met:

    • If I take the length of thetaamount + 1thedpArray recursion.
    • Each index represents the amount recurred to.
    • Each element is the number of combinations of coins.
    • 0The position is the initial state, set to1, indicates that both from1The number of combinations starts to recurse.

  2. We can break it down by coin type recursively:

    • COINS1:,1,1,1,1,1 [1]
    • COINS2:,0,1,0,1,0 [1]
    • COINS5:,0,0,0,0,1 [1]
    • COINS1,2:,1,2,2,3,3 [1]
    • COINS1,2,5:,1,2,2,3,4 [1]

  3. The recursive method is as follows:

    • Count each coin denomination in turncoinIs the recursive result of.
    • The current amountiFrom thei - coinaddedcoinAnd come.
    • Number of current coin combinationsdp[i]Theta is the same thing as the last coiniThe combination of severaldp[i], plusi - coinThe combination of severaldp[i - coin]And come.
    • The state transition equation is:dp[i] = dp[i] + dp[i - coin].
/ * * *@param {number} amount
 * @param {number[]} coins
 * @return {number}* /
var change = function (amount, coins) {
  // Keep using coin combinations from 0 to amount
  // The array holds the number of coin combinations available for each amount
  // The initial state is 0 because there is no recursion
  let dp = new Array(amount + 1).fill(0);
  // Set position 0 to 1, since the first push starts with the amount of coin
  // the state transition equation is dp[I] = dp[I] + dp[i-coin].
  // Dp [0] = 1
  dp[0] = 1;

  // Count the number of ways each coin can be combined into an amount
  for (const coin of coins) {
    // An amount less than coin cannot be combined by coin
    // Push all the way to amount to see how many ways the current coin can be combined to form amount
    for (let i = coin; i <= amount; i++) {
      dp[i] =
        // The number of ways in which coins can be combined to create the current amount
        dp[i] +
        // The current amount must be a combination of i-coins and coins added
        // That is, the current amount is based on i-coins, so you need to bring the number of i-coins combineddp[i - coin]; }}// The number of methods that are finally combined to amount, at the amount location
  return dp[amount];
};
Copy the code