“This is the 8th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

The title

Give coins of different denominations and a total amount. Write a function to calculate the number of coin combinations that add up to the total. 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 make a total amount: 5=5 5=2+2+1 5=2+1+1 5=1+1+1+1+1 +1

Example 2: Input: Amount = 3, Coins = [2] Output: 0

Example 3: Input: Amount = 10, Coins = [10] Output: 1

Note that you can assume:

  • 0 <= amount <= 5000
  • 1 <= coin value <= 5000
  • There are no more than 500 types of coins
  • The result conforms to a 32 – bit signed integer

Their thinking

A backpack has an amount and n items of coins, each item weighs coins[I], and each item has an infinite number of coins. How many ways can a backpack be filled exactly?

N is the length of coins

1. Dp array definition

Dp [I][j] = x, indicating that for the first I items, when the backpack capacity is J, there are x ways to assemble at most, that is, only the face value of the first I coins in Coins can be used. There are X ways to collect the amount J

2. Selection and status

Choice: Pack in backpack or not pack in backpack

States: backpack capacity and optional items (there are two states, so DP uses a 2d array)

State transition

Dp [I][j]= DP [I][j-1]; DP [I]= DP [I][J-1]; J-coins [i-1] indicates the current backpack capacity J minus the current weight of COINS [i-1]. (Since I starts from 1, the index of Coins is i-1, indicating the value of the i-1 coin.) If coins[I] are not stored in the backpack, the calculation is dp[I][j]= DP [i-1][j], indicating the same result as before

3. base case dp[0][..] = 0 if no coin denomination is used, no sum can be collected, i.e. 0 sum and dp[..] [0]=1 (dp[0][0]=1) If the target sum to be raised is 0, there is only one method

function change(amount, coins) {
    let n = coins.length;
    // Define and initialize a two-dimensional array
    const dp = [];
    for (let i = 0; i < n + 1; i++) {
        dp[i] = [];
        for (let j = 0; j < amount + 1; j++) {
            // base case
            if (i === 0) {
                dp[0][j] = 0;
            }
            // base case
            if (j === 0) {
                dp[i][0] = 1;
            } else {
                dp[i][j] = 0; }}}console.log(dp);
    
    / / to make a choice
    for (let i = 1; i < n + 1; i++) {
        for (let j = 1; j < amount + 1; j++) {
            // If the selected i-th coin is larger than the amount you want to collect, you can only choose not to load the coin
            if (j - coins[i - 1] < 0) {
                dp[i][j] = dp[i - 1][j];
            } else {
                // dp[I][j] = n
                dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]. }}}// The answer to your question
    return dp[n][amount];
}
Copy the code