【Day 63 】2024-10-16 - 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

[Fightforcoding]

class Solution: # T: O(n * amount) S: O(amount) def coinChange(self, coins: List[int], amount: int) -> int:

    DP = {0:0}        
    def backtrack(remainder):

        if remainder in DP:
            return DP[remainder]

        res = inf
        for c in coins:
            if remainder - c >= 0 :
                res = min(res, 1 + backtrack(remainder-c))             
        DP[remainder] = res
        return res

    res = backtrack(amount)
    return res if res != inf else -1

class Solution: # T: O(n * amount) S: O(amount) 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 c in coins:
            if i - c >= 0:
                DP[i] = min(DP[i], 1 + DP[i-c])

    return DP[-1] if DP[-1] != amount+1 else -1

[jialigogogo]

思路

动态规划构建一个数组，其中每个元素表示组成对应金额所需的最少硬币数。组成金额 0 不需要任何硬币 ，对于每个金额，尝试使用所有可用的硬币面额来更新最少硬币数的值。

代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;
        }
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

复杂度

时间复杂度：O(amount * coins.length)

空间复杂度：O(amount)

[qiaoeve]

思路：递归搜索 代码： ‘class Solution: def coinChange(self, coins: List[int], amount: int) -> int: def dfs(i: int, c: int) -> int: if i < 0: return 0 if c == 0 else inf if c < coins[i]: return dfs(i - 1, c) return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1) ans = dfs(len(coins) - 1, amount) return ans if ans < inf else -1’ 复杂度：O(n⋅amount)