This is the 10th day of my participation in the genwen Challenge

Topic describes

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

Example 2:

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

Example 3:

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

Note:

You can assume:

  • 0
    Or less \le     amount(Total amount)
    Or less \le     5000
  • 1
    Or less \le     coin(Coin denomination)
    Or less \le     5000
  • There are no more than 500 types of coins
  • The result conforms to a 32 – bit signed integer

Their thinking

In this problem, given the total amount and the array coinw, calculate the number of coin combinations that the sum of the amount equals. Each element of Coins can be selected multiple times, regardless of the order of elements selected. Therefore, this question needs to calculate the number of combinations of coins selected.

The number of possible combinations can be calculated by dynamic programming. Use dp[x]dp[x]dp[x] to represent the number of coin combinations whose sum is equal to XXX. The objective is to find dp[amount]dp[amount]dp[amount].

The boundary of dynamic programming is dp[0]=1dp[0]=1dp[0]=1. The sum is 000 only if no coins are selected, so there are only 111 coin combinations.

For coincoincoin denomination, when coin≤ I ≤amountcoin \le I \le amountcoin ≤ I ≤amount, if there is a combination of coins whose sum is equal to I − Coini −coini−coin, Add a coin with the denomination coincoincoin to the coin combination and you get a coin combination with the sum of the coins equal to III. Therefore, you need to traverse Coins, updating the value of each element greater than or equal to that denomination in the ARRAY DPDPDP for each denomination.

Thus, the dynamic programming approach can be obtained:

  • Dp [0]=1dp[0]=1dp[0]=1;
  • traversecoinsFor each of these elementscoin, perform the following operations:
  • traverse
    i i     从 coin 到 amountThat will be
    d p [ i – c o i n ] Dp [I – “]     The value added to
    d p [ i ] dp[i]     .
  • The result is dp[amount]dp[amount].

code

C + + code

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        dp[0] = 1;
        for (int& coin : coins) {
            for (inti = coin; i <= amount; i++) { dp[i] += dp[i - coin]; }}returndp[amount]; }};Copy the code