【Day 63 】2023-08-11 - 322. 零钱兑换

[azl397985856]

322. 零钱兑换

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回  -1。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0
示例 4：

输入：coins = [1], amount = 1
输出：1
示例 5：

输入：coins = [1], amount = 2
输出：2
 

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

[GuitarYs]

class Solution:
    def coinChange(self, coins, amount):
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

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

        if dp[amount] == float('inf'):
            return -1
        else:
            return dp[amount]

[freesan44]

class Solution {
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
                var dp = [Int](repeating: amount + 1, count: amount + 1)
        dp[0] = 0

        for i in 1...amount {
            for coin in coins {
                if i >= coin {
                    dp[i] = min(dp[i], dp[i - coin] + 1)
                }
            }
        }

        return dp[amount] == amount + 1 ? -1 : dp[amount]
    }
}

[Diana21170648]

思路

可以重复取值的完全背包

代码

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

        for i in range(1,amount+1):
            for coin in coins:
                if i>=coin:#还没有达到目标值则更新dp，取小值
                    dp[i]=min(dp[i],dp[i-coin]+1)#dp是要取的最少硬币数，在统计数量
        return -1 if dp[amount]==amount+1 else dp[amount]

复杂度分析

• 时间复杂度：O(N*amount)，其中 N 为len(coins)。
• 空间复杂度：O(amount),背包容量大小就是空间复杂度

[Fuku-L]

代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount < 1){
            return 0;
        }
        return coinChange(coins, amount, new int[amount]);
    }
    private int coinChange(int[] coins, int rem, int[] count){
        if(rem < 0){
            return -1;
        }
        if(rem == 0){
            return 0;
        }
        if(count[rem - 1] != 0){
            return count[rem - 1];
        }
        int min = Integer.MAX_VALUE;
        for(int coin:coins){
            int res = coinChange(coins, rem - coin, count);
            if(res >= 0 && res < min){
                min = 1 + res;
            }
        }
        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];
    }
}

[passengersa]

代码： var coinChange = function(coins, amount) { coins.sort((a,b) => a-b); if (amount === 0) return 0; if (amount < coins[0]) return -1; let ans = 999999; d(amount, coins.length - 1, 0, coins); function d(num, index, len, coins) { if (num === 0) { ans = Math.min(ans, len); return; }; if (index < 0) return; for (let k=Math.floor(num / coins[index]); k >=0 && k + len < ans; k--) { d(num - coins[index] * k, index - 1, len + k, coins); } } return ans === 999999 ? -1 : ans; };

[Beanza]

var coinChange = function(coins, amount) { coins.sort((a,b) => a-b); if (amount === 0) return 0; if (amount < coins[0]) return -1; let ans = 999999; d(amount, coins.length - 1, 0, coins); function d(num, index, len, coins) { if (num === 0) { ans = Math.min(ans, len); return; }; if (index < 0) return; for (let k=Math.floor(num / coins[index]); k >=0 && k + len < ans; k--) { d(num - coins[index] * k, index - 1, len + k, coins); } } return ans === 999999 ? -1 : ans; };

[Momogir]

#时间复杂度O(n*amount),空间复杂度O(n*amount)
#F(s)为总问题，表示当金额为s时候，选取的最少硬币数目
#F(s1),F(s2),F(s3)...为子问题
#关键在于初始化dp矩阵的x轴和y轴
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n=len(coins)
        dp=[[float('inf')]*(amount+1) for _ in range(n)]
        for i in range(n):dp[i][0]=0
        for j in range(amount+1):
            if coins[0]==j: 
                dp[0][j]=1

        for i in range(n):
            for j in range(amount+1):
                if coins[i]<=j:
                    dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i]]+1)
                else:
                    dp[i][j]=dp[i-1][j]
        # print(dp)
        return dp[-1][-1] if dp[-1][-1]!=float('inf') else -1

[Alexno1no2]

    def coinChange(self,coins: List[int], amount: int) -> int:
        self.dp = [amount + 1] * (amount + 1)
        # 数组大小为 amount+1，初始值也为 amount+1
        self.dp[0] = 0
        # base case
        # 初始值为0
        # 外层 for 循环在遍历所有状态的所有取值
        for i in range(len(self.dp)):
            # 内层 for 循环在求所有选择的最小值
            for coin in coins:
                # 子问题无解，跳过
                if i - coin < 0:
                    continue
                self.dp[i] = min(self.dp[i], 1 + self.dp[i - coin]) 

        # 如果结果是初始值，则表示没有找到解。
        return -1 if self.dp[amount] == amount + 1 else self.dp[amount]