【Day 64 】2023-04-18 - 518. 零钱兑换 II

[azl397985856]

518. 零钱兑换 II

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/coin-change-2/

前置知识

暂无

题目描述

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:

输入: amount = 10, coins = [10]
输出: 1
 

注意:

你可以假设：

0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数

[huizsh]

class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [0] * (amount + 1) dp[0] = 1

    for j in range(len(coins)):
        for i in range(1, amount + 1):
            if i >= coins[j]:
                dp[i] += dp[i - coins[j]]

    return dp[-1]

[airwalkers]

class Solution {
    public int change(int amount, int[] coins) {
        int m = coins.length, n = amount;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= n; j++) {
                dp[i][j] += dp[i - 1][j];
                if (j >= coins[i - 1]) {
                    dp[i][j] += dp[i][j - coins[i - 1]];
                }
            }
        }
        return dp[m][n];
    }
}

[aoxiangw]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for i in range(len(coins) -1, -1, -1):
            nextDP = [0] * (amount + 1)
            nextDP[0] = 1

            for a in range(1, amount + 1):
                nextDP[a] = dp[a]
                if a - coins[i] >= 0:
                    nextDP[a] += nextDP[a - coins[i]]
            dp = nextDP
        return dp[amount]

time, space: O(amount * len(coins)), O(amount)

[chanceyliu]

思路

动态规划

代码

function change(amount: number, coins: number[]): number {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] += dp[i - coin];
    }
  }
  return dp[amount];
}

复杂度分析

• 时间复杂度：O(amount * n) n 为 coins 数组长度
• 空间复杂度：O(amount)

[Abby-xu]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount+1)
        dp[0] =1

        for i in range(len(coins)-1,-1,-1):
            for j in range(1,amount+1):
                if j - coins[i] >=0:
                    dp[j] += dp[j-coins[i]]

        return dp[amount]

[Meisgithub]

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
        for (int i = 0; i <= n; ++i)
        {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= amount; ++j)
            {
                // dp[i][j] += dp[i - 1][j];
                int k = 0;
                while (j - k * coins[i - 1] >= 0)
                {
                    dp[i][j] += dp[i - 1][j - k * coins[i - 1]];
                    k++;
                }
            }
        }
        return dp[n][amount];
    }
};

[FireHaoSky]

思路：动态规划

代码：python

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [1] + [0] * amount

        for coin in coins:
            for i in range(coin, amount+1):
                dp[i] += dp[i-coin]

        return dp[amount]

复杂度分析：

"""
时间复杂度：O(amount*len(coins))
空间复杂度：O(amount)
"""

[csthaha]

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1; // amount = 0 什么也不选结果 1
    for(let item of coins) {
        for(let i = item; i <= amount; i++) {
            dp[i] = dp[i] + dp[i - item]
        }
    }
    return dp[amount]
};

[Diana21170648]

思路

动态规划，背包，求最大组合数，dp初始化为0，dp[0]=1

class Solution:
    def coinchange2(self,amount,coins)->int:
        dp=[0]*(amount+1)
        dp[0]=1
        for i in range(len(coins)-1,-1,-1):
            for j in range (1,amount+1):

                if j >= coins[i]:
                    dp[j]+=dp[j-coins[i]]
                    return dp[amount]

Solution().coinchange2()

**复杂度分析**
- 时间复杂度：O(nums(coins)*amount)，其中 N 为数组长度。
- 空间复杂度：O(amount)

[kofzhang]

思路

动态规划，和昨天的题差不多

复杂度

时间复杂度：O(n*amount) 空间复杂度：O(amount)

代码

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        if amount == 0:
            return 0
        dp = [0]*(amount+1)
        dp[0]=1
        for c in coins:
            for i in range(c,amount+1):
                dp[i] += dp[i-c]
        return dp[amount]

[harperz24]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1

        for j in range(len(coins)):
            for i in range(1, amount + 1):
                if i >= coins[j]:
                    dp[i] += dp[i - coins[j]]

        return dp[-1]

[Size-of]

/**

• @param {number} amount
• @param {number[]} coins
• @return {number} */ var change = function(amount, coins) { const dp = new Array(amount + 1).fill(0); dp[0] = 1; for (const coin of coins) { for (let i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount]; };

[JasonQiu]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for i in range(1, amount + 1):
                if coin <= i:
                    dp[i] += dp[i - coin]
        return dp[amount]

Time: O(n*amount) Space: O(amount)

[zhangyu1131]

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;// 0有一种实现方式
        for (auto coin : coins)
        {
            for (int i = 1; i <= amount; ++i)
            {
                if (i >= coin)
                {
                    dp[i] += dp[i - coin];
                }
            }
        }
        return dp[amount];
    }
};

[bookyue]

TC: O(nm)
SC: O(m)

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }

[NorthSeacoder]

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
    //dp[j]:总金额为 j 有 dp[j]种方式
    const dp = new Array(amount + 1).fill(0);
    //金额为 0 时有 1 种方式
    //dp[j]就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。
    dp[0] = 1;
    for(let i = 0;i<coins.length;i++){
        for(let j = coins[i];j<=amount;j++){
            dp[j]+=dp[j-coins[i]]
        }
    }
    return dp[amount]
};

[lp1506947671]

Python Code:

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1

        for j in range(len(coins)):
            for i in range(1, amount + 1):
                if i >= coins[j]:
                    dp[i] += dp[i - coins[j]]

        return dp[-1]

复杂度分析

令n是coins的数量, m是amount

时间复杂度: O(m*n)

空间复杂度: O(m)

[tzuikuo]

思路

动态规划

代码

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1);
        int n=coins.size();
        for(int j=0;j<=amount;j++){
            if(j%coins[0]==0) dp[j]=1;
        }
        for(int i=1;i<n;i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j]=dp[j]+dp[j-coins[i]];
            }
        }

        return dp[amount];
    }
};

复杂度分析 待定

[kangliqi1]

class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [0] * (amount + 1) dp[0] = 1

    for j in range(len(coins)):
        for i in range(1, amount + 1):
            if i >= coins[j]:
                dp[i] += dp[i - coins[j]]

    return dp[-1]

[snmyj]

class Solution {
public:
    int change(int amount, vector<int>& coins) {
         vector<int> dp(6000,0);
         dp[0]=0;
         sort(coins.begin(),coins.end());
         for(int i=1;i<=amount;i++){
         for(auto x:coins){
               if((i-x)==0) 
                   dp[i]++;

               if(((i-x)>0)&&dp[i-x]!=0){
                   dp[i]+=dp[i-x];
               }
         }
         }
         return dp[amount];
    }
};

[Lydia61]

518. 零钱兑换

代码

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1

        for j in range(len(coins)):
            for i in range(1, amount + 1):
                if i >= coins[j]:
                    dp[i] += dp[i - coins[j]]

        return dp[-1]

复杂度分析

• 时间复杂度: O(coins * amount)

• 空间复杂度: O(amount)

[joemonkeylee]

思路

dp

代码

       public int change(int amount, int[] coins) {
             int m = coins.Length, n = amount;
            int[][] dp = new int[m + 1][];
            for (int i = 0; i < dp.Length; i++)
            {
                dp[i] = new int[n+1];
            }
            for (int i = 1; i <= m; i++)
            {
                dp[i][0] = 1;
                for (int j = 1; j <= n; j++)
                {
                    dp[i][j] += dp[i - 1][j];
                    if (j >= coins[i - 1])
                    {
                        dp[i][j] += dp[i][j - coins[i - 1]];
                    }
                }
            }
            return dp[m][n];
        }

• 时间复杂度：O(amount * n)
• 空间复杂度：O(amount)

[Jetery]

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> vc(amount + 1);
        vc[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++){
                vc[i] += vc[i - coin];
            }
        }
        return vc[amount];
    }
};

[bingzxy]

代码

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

复杂度分析

• 时间复杂度：O(amount * n)
• 空间复杂度：O(amount)

[Fuku-L]

代码

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int coin: coins){
            for(int i = coin; i<=amount; i++){
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

复杂度分析

• 时间复杂度：O(amount*n)，其中amount为总金额， n为数组coins的长度。
• 空间复杂度：O(amount)

[X1AOX1A]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1

        for j in range(len(coins)):
            for i in range(1, amount + 1):
                if i >= coins[j]:
                    dp[i] += dp[i - coins[j]]

        return dp[-1]

[sye9286]

思路

动态规划

代码

var change = function(amount, coins) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (const coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
};

复杂度分析

• 时间复杂度：O(M*N)
• 空间复杂度：O(N)

[61hhh]

思路

dp问题

代码

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int coin : coins){
            for(int i=coin;i<=amount;i++){
                dp[i]+=dp[i-coin];
            }
        }
        return dp[amount];
    }
}

复杂度分析

• 时间复杂度：O(coins.length amount)，coins数组长度 金额。
• 空间复杂度：O(amount)

[RestlessBreeze]

code

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        dp[0] = 1;
        for (int i = 0; i < coins.size(); i++)
        {
            for (int j = coins[i]; j < amount + 1; j++)
            {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount] == 0 ? 0 : dp[amount];
    }
};