【Day 64 】2023-08-12 - 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 位符号整数

[yetfan]

代码

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

        return dp[amount]

[Diana21170648]

思路

滚动数组优化，动态规划，注意硬币倒着往前选择

代码

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp=[0]*(amount+1)#求max，dp初始化为0
        dp[0]=1
        for j in range(len(coins)):#硬币大小
            for i in range(1,amount+1):#背包大小
                if i>=coins[j]:
                    #dp[i - coins[j]] 表示在从总金额中减去当前硬币面额的值后，剩余的金额的方法数
                    #硬币面额小于当前面额，才能通过硬币组合实现amount
                    dp[i]+=dp[i-coins[j]]#选择i，dp[i]表示凑成zmount的次数
        return dp[-1]

复杂度分析

• 时间复杂度：O(n*amount)，n=len(coins)。
• 空间复杂度：O(amount),amount即为背包的大小

[GuitarYs]

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

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

        return dp[amount]

[Momogir]

#时间复杂度O(n*amount),空间复杂度O(n*amount)
#F(s)为总问题，表示当金额为s时候，选取的最多组合数字
#F(s1),F(s2),F(s3)...为子问题
#关键在于初始化dp矩阵的x轴和y轴
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n=len(coins)
        dp=[[0]*(amount+1) for _ in range(n)]
        for i in range(n):dp[i][0]=0
        for j in range(amount+1):
            res=j%coins[0]
            if res == 0: 
                dp[0][j]=1
        # print(dp)
        for i in range(1,n):
            for j in range(amount+1):
                #使用当前coins[i]
                if j >= coins[i]:
                    dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]]
                else:
                    #不使用当前coins[i]
                    dp[i][j]=dp[i-1][j]

        return dp[-1][-1]

[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];
    }
}

[Alexno1no2]

抄答案

# dp[j] 代表装满容量为j的背包有几个硬币组合
# 移位方程：dp[j] = dp[j] + dp[j - coin] 当前填满j容量的硬币组合数 = 之前填满j容量的硬币组合数 + 填满j - coin容量的硬币组合数和当前硬币硬币的加入，可以把j -硬币容量的组合数字加入输入 和01背包差不多，唯一的不同点在于硬币可以重复使用，一个逆序一个正序的区别
# 返回dp[-1]，原来dp[金额]

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