Make writing a habit together! This is the 9th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

The title

Change II

You are given an integer array coins to indicate different denominations and an integer amount to indicate the total amount.

Please count and return the number of coin combinations that add up to the total. If no coin combination makes up the total, return 0.

Suppose there are an infinite number of coins of each denomination.

The problem data guarantees that the result is a 32-bit signed integer.

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 +1Copy the code

Example 2:

Input: Amount = 3, Coins = [2] Example 3: Input: Amount = 10, Coins = [10] Output: 1Copy the code

Answer key

Analysis of the problem solving

Answer:

  1. The longest common subsequence problem is a typical two dimensional dynamic programming problem.
  2. (2) The number of coins that amount to an amount is the same as the number of coins in the array coins. American and Russian elements in Coins can be selected multiple times, regardless of the order of elements. Therefore, this topic needs to calculate the number of combinations selected for coins.
  3. We can use dynamic programming to calculate the number of groups. Use dp[x] as the number of combinations equal to x, and then find dp[amount].
  • The boundary value of dynamic programming dp[0] = 1. Only when no coins are selected, the sum of the amounts is 0, so there is only one coin combination.
  • For coins of denomination, only when coin <= I <= Annont, if there is a coin combination that only adds up to i-coin, add a coin of denomination to the coin combination. So you get a combination of coins that only add up to I. Therefore, you need to traverse Coins for each denomination. , updates the value of each element in array DP that is heavy or equal to that denomination.
  • 1). Initialize dp[0] =1; 2). Traversal coins, for each coin in it, do the following: – Traversal I from coin to amount, and add the value of dp[i-coin] to dp[I] 3). The final value is dp[amount].
  1. Consider and note whether there is a problem with double counting for the above process. No, because the outer loop traverses the value of coins, while the inner loop traverses the sum of different amounts. When calculating the value of DP [I], it can ensure that the amount is only the allowance of I. Since the order is determined, there will be no repeated arrangement.

Time complexity: O(M*N) Space complexity: O(M)

The problem solving code

The solution code is as follows (there are detailed notes in the code) :

int change(int amount, int* coins, int coinsSize){
        / / array
        int dp[amount +1];
        // Initialize the array
        memset(dp, 0.sizeof(dp));
        // Initialize the first value
        dp[0] = 1;
        // All the change
        for (int i = 0; i < coinsSize; i++) {
               // Change combination
               for (intj = coins[i]; j <= amount; j++) { dp[j] += dp[j - coins[i]]; }}return dp[amount];
}
Copy the code

Feedback results after submission (because the topic has not been optimized, the performance is mediocre) :

The reference information

  • 518. Change for II
  • Dynamic programming