“This is the 17th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

1, the title

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]Copy the code

Example 3:

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

Tip:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coinsAll values inEach other is not the same
  • 0 <= amount <= 5000

2, train of thought

(Dynamic programming, full knapsack)

A two-dimensional analysis

The state represents: f[I][j] represents the number of alternatives set of all alternatives selected from the previous I coins, and the total amount is exactly J.

F [n][amount] is the number of choices that amount to the first n coins.

Set division:

According to the i-th coin can choose 0,1, 2, 3 ，，，，k partition set f[I][j]. Where k*coin[I] <= j, that is to say, if the backpack can hold, enumerating the i-th coin can choose several.

  • The firstiKind of coin to choose0A,f[i][j] = f[i-1][j]
  • The firstiKind of coin to choose1A,f[i][j] = f[i-1][j - coins[i]]
  • The firstiKind of coin to choosekA,f[i][j] = f[i-1][j - k*coins[i]]

State calculation:

[I] [j] f = f [I – 1] [j] [I – 1) + f [j – COINS [I]] + f [I – 1] [j – 2 * COINS [I]],,,,,,,, [I – 1) + f [j – k * COINS [I]]. Initialization conditions:

  • f[0][0] = 1, the use of0Kind of coins, yeah0Yuan is also a solution.

Time complexity analysis: O(amount2∗n)O(amount^2*n)O(amount2∗n), where amountamountAmount is the total amount and NNN is the length of array Coinscoinscoins.

3. Two-dimensional c++ code

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>>f(n + 1.vector<int>(amount + 1 , 0));
        f[0] [0] = 1;  // Using 0 currencies and collecting 0 yuan is also a solution
        for(int i = 1; i <= n; i++)
        {
            int v =coins[i - 1];
            for(int j = 0; j <= amount; j++)
                 for(int k = 0; k*v <= j; k++)
                   f[i][j] += f[i- 1][j-k*v];    // State calculation equation
        }
        returnf[n][amount]; }};Copy the code

4. Two-dimensional Java code

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] f = new int[n + 1][amount + 1];
        f[0] [0] = 1;   // Using 0 currencies and collecting 0 yuan is also a solution
        for (int i = 1; i <= n; i++) {
            int v = coins[i - 1];
            for (int j = 0; j <= amount; j++) 
                for (int k = 0; k * v <= j; k++) 
                    f[i][j] += f[i - 1][j - k * v];  // State calculation equation
        }
        returnf[n][amount]; }}Copy the code

5. One-dimensional optimization

The time complexity of two-dimensional complete knapsack solution is high, so one-dimensional optimization is considered.

V is the face value of the i-th coin

f[i][j] = f[i-1][j] + f[i-1][j-v]+f[i-1][j-2v]+,,,,,+f[i-1][j-kv])

f[i][j-v] = f[i-1,[j-v]+f[i-1][j-2v]+,,,,,+f[i-1][j-kv])

Therefore:

f[i][j] = f[i-1][j]+f[i][j-v])

Here is:

Remove the dimension of item type, and the state calculation equation is: F [j] = F [j] + F [J-V]

Time complexity analysis: O(Amount ∗n)O(amount*n)O(amount∗n), where amountamountAmount is the total amount and NNN is the length of array Coinscoinscoins.

6. One-dimensional c++ code

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int>f(amount + 1);
        f[0] = 1; //f[0][0] = 1;
        for(int i = 1; i <= coins.size(); i++)
        {
            int v =coins[i - 1];
            for(int j = v; j <= amount; j++)
                f[j] += f[j - v];
        }
        returnf[amount]; }};Copy the code

One-dimensional Java code

class Solution {
    public int change(int amount, int[] coins) {
        int[] f = new int[amount + 1];
        f[0] = 1; //f[0][0] = 1;
        for(int i = 1; i <= coins.length; i++)
        {
            int v =coins[i - 1];
            for(int j = v; j <= amount; j++)
                f[j] += f[j - v];
        }
        returnf[amount]; }}Copy the code

518. Change for II