【Day 63 】2023-01-02 - 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

[zjsuper]

class Solution: def coinChange(self, coins: List[int], amount: int) -> int:

bfs shortest path, first meet ans will be the answer

    if not amount:
        return 0
    visit = set()
    queue = deque([(amount,0)])
    while queue:
        a,nc = queue.popleft()
        if a == 0:
            return nc

        for c in coins:
            if a-c <0 or a-c in visit:
                continue
            queue.append((a-c,nc+1))
            visit.add(a-c)
    return -1

[Ryanbaiyansong]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        f = [inf] * (amount + 1)
        f[0] = 0
        for i, v in enumerate(coins):
            for j in range(v, amount + 1):
                f[j] = min(f[j], f[j - v] + 1)

        return f[-1] if f[-1] != inf else -1

[whoam-challenge]

class Solution: def coinChange(self, coins: List[int], amount: int) -> int: @functools.lru_cache(amount) def dp(rem) -> int: if rem < 0: return -1 if rem == 0: return 0 mini = int(1e9) for coin in self.coins: res = dp(rem - coin) if res >= 0 and res < mini: mini = res + 1 return mini if mini < int(1e9) else -1

    self.coins = coins
    if amount < 1: return 0
    return dp(amount)

[JancerWu]

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

    }
}

[zywang0]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        f = [inf] * (amount + 1)
        f[0] = 0
        for i, v in enumerate(coins):
            for j in range(v, amount + 1):
                f[j] = min(f[j], f[j - v] + 1)

        return f[-1] if f[-1] != inf else -1

[FlipN9]

/**
    S: amount, N: amount of different coins
    TC: (SN)    SC: O(S)
*/
class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        int INF = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        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];
    }
}

[guowei0223]

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

[snmyj]

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,amount*2);
        dp[0]=0;
        if(amount==0) return 0;
        for(int i=1;i<=amount;i++){
            for(auto x:coins){
                if(i<x) continue;
                dp[i]=min(dp[i],dp[i-x]+1);
            }
        }

       return dp[amount]==amount*2?-1:dp[amount];
    }
};

[mayloveless]

思路

完全背包问题，最少需要多少物品的最值问题，状态转移方程: dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-weight[i]] + 1 )

代码

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    // 完全背包问题，最少需要多少物品的最值问题
    const n = coins.length
    // dp的值为最少硬币个数
    const dp = Array(n).fill().map(() => Array(amount+1).fill(Number.MAX_SAFE_INTEGER));
    // 如果只有1种硬币
    for (let c = 0; c <= Math.floor(amount/coins[0]); ++c) {
        dp[0][c*coins[0]] = c
    }

    for (let i = 1; i < n; ++i) {
        for (let j = 0; j <= amount; ++j) {
            let k = Math.floor(j/coins[i])
            for (let c = 0; c <= k; ++c) {
                const last = dp[i-1][j-c*coins[i]];
                 if (last + c < dp[i][j] && last !== Number.MAX_SAFE_INTEGER) {
                    dp[i][j] = last + c
                }
            }
        }
    }    

    const res = dp[n-1][amount];
    return res === Number.MAX_SAFE_INTEGER ? -1 : res;
};

复杂度

时间：O(namountk) 空间：O(n*amount)

[A-pricity]

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
const coinChange = (coins, amount) => {
    if(!amount) {
        return 0;
    }

    let dp = Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for(let i =0; i < coins.length; i++) {
        for(let j = coins[i]; j <= amount; j++) {
            dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}

[Abby-xu]

思路

DP

代码

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0] + [float('inf') for i in range(amount)]
        for i in range(1, amount+1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i-coin] + 1)
        if dp[-1] == float('inf'):
            return -1
        return dp[-1]

复杂度

...

[GG925407590]

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

[bookyue]

code

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin < 0) continue;

                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }

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

[klspta]

class Solution {
    public int coinChange(int[] coins, int m) {
        int[] dp = new int[m + 1];
        Arrays.fill(dp, m + 1);
        dp[0] = 0;
        for(int v : coins){
            for(int j = v; j <= m; j++){
                dp[j] = Math.min(dp[j], dp[j - v] + 1);
            }
        }
        if(dp[m] > m){
            return -1;
        }
        return dp[m];
    }
}

[Elsa-zhang]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        dp = [[amount + 1]*(amount+1) for _ in range(n+1)]

        for i in range(n+1):
            dp[i][0] = 0

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

        if dp[n][amount] == amount+1:
            return -1
        return dp[n][amount]

[saitoChen]

代码

const coinChange = (coins, amount) => {
    if(!amount) {
        return 0;
    }

    let dp = Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for(let i =0; i < coins.length; i++) {
        for(let j = coins[i]; j <= amount; j++) {
            dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}

[RestlessBreeze]

code

class Solution {
    vector<int>count;
    int dp(vector<int>& coins, int rem) {
        if (rem < 0) return -1;
        if (rem == 0) return 0;
        if (count[rem - 1] != 0) return count[rem - 1];
        int Min = INT_MAX;
        for (int coin:coins) {
            int res = dp(coins, rem - coin);
            if (res >= 0 && res < Min) {
                Min = res + 1;
            }
        }
        count[rem - 1] = Min == INT_MAX ? -1 : Min;
        return count[rem - 1];
    }
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount < 1) return 0;
        count.resize(amount);
        return dp(coins, amount);
    }
};

[tiandao043]

思路

dp或dfs

代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // dp[i]表示组成金额 i 所需要最少的硬币数量
        vector<int> dp(amount+1,amount+1); // 大小，初值
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            for(int j=0;j<coins.size();j++){
                if(coins[j]<=i)
                    dp[i]=min(dp[i],dp[i-coins[j]]+1);
            }
        }
        return dp[amount]>amount?-1:dp[amount];
    }
};

class Solution {
public:
    vector<int>count;
    int dp(vector<int>& coins, int rem){
        if(rem<0)return -1;
        if(rem==0)return 0;
        if(count[rem-1]!=0)return count[rem-1];
        int minCost = INT_MAX;
        for(int coin:coins){
            int res = dp(coins, rem - coin);                    
            if(res >= 0 && res<minCost){
                minCost=res+1;
            }
        }
        count[rem-1] = minCost == INT_MAX ? -1:minCost;
        return count[rem-1];
    }
    int dfs(vector<int>& coins, int amount,int ind){
        if(amount == 0)return 0;
        if(ind < coins.size() && amount > 0){
            int maxVal = amount / coins[ind];
            int minCost = INT_MAX;
            for(int x = 0;x <= maxVal; x++){
                if(amount >= x * coins[ind]){
                    int res = dfs(coins, amount - x * coins[ind], ind+1);                    
                    if(res != -1){
                        minCost = min(minCost,res + x);cout<<res<<endl;
                    }
                }
            }
            return minCost == INT_MAX ? -1:minCost;
        }
        return -1;
    }
    int coinChange(vector<int>& coins, int amount) {
        count.resize(amount);
        return dp(coins,amount);
    }
};

O(N∗amount) O(amount)

[MaylingLin]

思路

---

完全背包

代码

class Solution(object):
    def coinChange(self, coins, amount):
        dp = [amount + 1] * (amount+1)
        dp[0] = 0
        for i in range(1, amount+1):
            for coin in coins:
                if i >= coin:
                    dp[i] = min(dp[i], dp[i-coin]+1)
        return -1 if dp[amount] == amount + 1 else dp[amount]

复杂度

---

• Time: $O(N*amount)$，N为物品个数即硬币种类，amount为总金额即背包大小。
• Space: $O(amount)$

[paopaohua]

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 自底向上的动态规划
        if(coins.length == 0){
            return -1;
        }

        // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
        int[] memo = new int[amount+1];
        // 给memo赋初值，最多的硬币数就是全部使用面值1的硬币进行换
        // amount + 1 是不可能达到的换取数量，于是使用其进行填充
        Arrays.fill(memo,amount+1);
        memo[0] = 0;
        for(int i = 1; i <= amount;i++){
            for(int j = 0;j < coins.length;j++){
                if(i - coins[j] >= 0){
                    // memo[i]有两种实现的方式，
                    // 一种是包含当前的coins[i],那么剩余钱就是 i-coins[i],这种操作要兑换的硬币数是 memo[i-coins[j]] + 1
                    // 另一种就是不包含，要兑换的硬币数是memo[i]
                    memo[i] = Math.min(memo[i],memo[i-coins[j]] + 1);
                }
            }
        }

        return memo[amount] == (amount+1) ? -1 : memo[amount];
    }
}

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins.length == 0){
            return -1;
        }

        // res[n]的值： 表示的凑成总金额为n所需的最少的硬币数
        int[] res = new int[amount+1];
        res[0] = 0;
        for(int i = 1; i <= amount;i++){
            int min = Integer.MAX_VALUE;
            for(int j = 0;j < coins.length;j++){
                if(i - coins[j] >= 0 && res[i-coins[j]] < min){
                    min = res[i-coins[j]] + 1;
                }
            }

            res[i] = min;
        }

        return res[amount] == Integer.MAX_VALUE ? -1 : res[amount];
    }
}

[Jetery]

class Solution {
public:
    int INF = 0x3f3f3f3f;
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> f(amount + 1);
        for (int i = 1; i <= amount; i++) f[i] = INF;
        for (int i = 1; i <= n; i++) {
            int val = coins[i - 1];
            for (int j = val; j <= amount; j++) {
                f[j] = min(f[j], f[j - val] + 1);
            }
        }
        return f[amount] == INF ? -1 : f[amount];
    }
};

[buer1121]

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

    return dp[amount] if dp[amount]<amount+1 else -1