This is the 31st day of my participation in the August Text Challenge.More challenges in August

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.

The sample

Input: Amount =5, Coins = [1, 2, 5] Input: Amount =5, Coins = [1, 2, 5] There are four ways to obtain the total amount: 5=5 5=2+2+1 5=2+1+1 5=1+1+1+1 Explanation: only 2 coins can not make up the total amount of 3. Input: Amount = 10, Coins = [10] Output: 1Copy the code

prompt

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • All values in coins are different
  • 0 <= amount <= 5000

Their thinking

The advanced version of 322. Small Change differs from it in that the former requires the least, while the latter requires the total number of coin combinations.

  1. Initialize thedp[]The array;
  2. Iterate over coin combinations;
  3. If the current coin is less thanamount, then contribute a force to the combination of price difference.

Code implementation

class Solution {
    public int change(int amount, int[] coins) {
        / / initialization
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        
        // Iterate over the coin combination
        for(int coin : coins){
            // The price range
            for(int i = coin; i <= amount; ++i){
                // Make a contributiondp[i] += dp[i - coin]; }}returndp[amount]; }}Copy the code

Complexity analysis

  • Time complexity: O(MN)O(MN)O(MN)
  • Space complexity: O(N)O(N)O(N)

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

Title source: leetcode-cn.com/problems/co…