【Day 63 】2022-02-12 - 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

[yetfan]

思路 dp[i]，即数值凑到 i 的最小硬币数， 对于n种硬币,每一种硬币面值 j ，dp[i] = dp[i-j] + 1, 所以n种硬币的可能性的，取最小值即为所求。因为要求最小值，所以默认设为 inf， 初始值dp[0] = 0

代码

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

复杂度 时间 O(amount * ncoins) 空间 O(amount)

[zwx0641]

class Solution { public int coinChange(int[] coins, int amount) { if (amount == 0) return 0; int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); dp[0] = 0;

    for (int i = 1; i < dp.length; 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] == amount + 1 ? -1 : dp[amount];
}

}

[CoreJa]

思路

• 滚动DP：常规背包问题，求和为amount的最小硬币个数，可用滚动DP完成。硬币数无限，故滚动DP直接从前往后遍历即可。具体情况和LC: 518完全一致，只是求和改成了求最大值。状态转移方程也非常类似，$dp[j]=max(dp[j-coins[i]]+1,dp[j])$，复杂度$O(n*amount)$
• 状态压缩+滚动DP：另类解法，复杂度很低$O(n*amount/min(coins))$，LC上用例的时间而言要快20倍。动规问题转换成了在已经给定硬币数量为i的情况下，是否存在解使其和为j。则有状态转移方程$dp[i][j]=0|dp[i-1][j-coins[k]],(0\leq k<len(coins))$。改为滚动DP+状态压缩的方程则为：$dp=dp|dp>>(j-coins[k]) ,(0\leq k<len(coins))$。从i=1开始找，只要dp的最后一位为1就return i。具体可以看我的题解：Python 52ms 状态压缩+动规 超过最快方法将近一倍时间

代码

class Solution:
    # 滚动DP：常规背包问题，求和为`amount`的最小硬币个数，可用滚动DP完成。硬币数无限，故滚动DP直接从前往后遍历即可。具体情
    # 况和LC: 518完全一致，只是求和改成了求最大值。状态转移方程也非常类似，$dp[j]=max(dp[j-coins[i]]+1,dp[j])$，
    # 复杂度$O(n*amount)$
    def coinChange1(self, coins: List[int], amount: int) -> int:
        dp = [0] + [float('inf')] * amount
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[-1] if dp[-1] != float('inf') else -1

    # 状态压缩+滚动DP：另类解法，复杂度很低$O(n*amount/min(coins))$，LC上用例的时间而言要快20倍。动规问题转换成了在已经给
    # 定硬币数量为`i`的情况下，是否存在解使其和为`j`。则有状态转移方程$dp[i][j]=0|dp[i-1][j-coins[k]],
    # (0\leq k<len(coins))$。改为滚动DP+状态压缩的方程则为：$dp=dp|dp>>(j-coins[k]) ,(0\leq k<len(coins))$。
    # 从`i=1`开始找，只要dp的最后一位为1就`return i`。
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = 1 << amount
        for n in range(amount // min(coins) + 1):
            if dp & 1:
                return n
            tmp = 0
            for coin in coins:
                tmp |= dp >> coin
            dp = tmp
        return -1

[zjsuper]

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

        for i  in range(1,amount+1):
            for j in coins:
                if j <=i:
                    dp[i] = min(dp[i],dp[i-j]+1)
        if dp[-1] == inf:
            return -1
        return dp[-1]

[ZacheryCao]

Idea

DP-bottom up

Code

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, INT_MAX);
        dp[0] = 0;
        for(auto j:coins){
            for(int i = j; i<=amount; i++){
                if(i-j>=0 and dp[i-j] != INT_MAX){
                    dp[i] = min(dp[i], dp[i-j]+1);
                }
            }
        }
        return dp[amount] == INT_MAX? -1:dp[amount];
    }
};

Complexity:

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

[cszys888]

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

time complexity: O(amount*n), n stands for length of coins space complexity: O(amount)

[Tesla-1i]

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

[yan0327]

func coinChange(coins []int, amount int) int {
    dp := make([]int,amount+1)
    for i:=1;i<len(dp);i++{
        dp[i] = 10001
    }
    for _,coin := range coins{
        for i:=coin;i<=amount;i++{
            dp[i] = min(dp[i],dp[i-coin]+1)
        }
    }
    if dp[amount] == 10001{
        return -1
    }
    return dp[amount]
}
func min(a,b int) int{
    if a  < b{
        return a
    }
        return b
}

[yijing-wu]

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

        findWay(coins,amount,0);

        if(res == Integer.MAX_VALUE){
            return -1;
        }
        return res;
    }

    public void findWay(int[] coins,int amount,int count){
        if(amount < 0){
            return;
        }
        if(amount == 0){
            res = Math.min(res,count);
        }

        for(int i = 0;i < coins.length;i++){
            findWay(coins,amount-coins[i],count+1);
        }
    }
}

[Hacker90]

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

    findWay(coins,amount,0);

    if(res == Integer.MAX_VALUE){
        return -1;
    }
    return res;
}

public void findWay(int[] coins,int amount,int count){
    if(amount < 0){
        return;
    }
    if(amount == 0){
        res = Math.min(res,count);
    }

    for(int i = 0;i < coins.length;i++){
        findWay(coins,amount-coins[i],count+1);
    }
}

}

[Tao-Mao]

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

[haixiaolu]

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

        for each_value in range(1, amount + 1):
            for current_coin in coins:
                if each_value - current_coin >= 0:
                    dp[each_value] = min(dp[each_value], 1 + dp[each_value - current_coin])

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

[xuhzyy]

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for coin in coins:
            for j in range(coin, amount + 1):
                dp[j] = min(dp[j], dp[j-coin] + 1)
        return dp[-1] if dp[-1] < amount + 1 else -1

[z1ggy-o]

思路

动态规划。

今天自己稀里糊涂的把状态和转移方程找出来了，实际上并没有分析到位。。。看来类型模板的总结确实有用。

正确的规模划分应该是反向而来的。即，假设我们已经有了一些拼凑成 target value 的组合了，那么，各个组合所需的硬币数为：对于每个 coin n，凑 (target - n) 值所需的最少硬币数 + 1.

继而，我们将状态 dp[n] 定义为，凑 n 值所需最少的硬币数。base state 为 dp[0] = 0，一个硬币都不选；其余状态的初始值设置为一个不可能出现的大值，例如 target + 1（硬币最小为 1，至多用 target 枚）。

状态转移方程为：dp[n] = min(dp[n], dp[n - c]), c 为每一种硬币的值。

无法拼凑的值会保持最开始我们初始化的状态，从而可以判断 target 值是否可以拼出来。

代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);

        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (auto n: coins) {
                if (n > i)
                    continue;
                dp[i] = min(dp[i], 1 + dp[i - n]);     
            }
        }
        return dp[amount] == (amount + 1) ? -1 : dp[amount];
    }
};

复杂度分析

• 时间：O(nc)，n 为需要拼凑的值，c 为 coin 的种类数。对于每个想要拼的值，我们都需要遍历一次 coin 数组。
• 空间：O(n)

[tongxw]

思路

记忆化递归

class Solution {
    public int coinChange(int[] coins, int amount) {
        Map<Integer, Integer> memo = new HashMap<>();
        return dfs(coins, amount, memo);
    }

    private int dfs(int[] coins, int amount, Map<Integer, Integer> memo) {
        if (amount == 0) {
            return 0;
        }
        if (memo.containsKey(amount)) {
            return memo.get(amount);
        }

        int min = Integer.MAX_VALUE;
        for (int coin: coins) {
            if (coin <= amount) {
                int count = dfs(coins, amount - coin, memo);
                if (count != -1) {
                    min = Math.min(min, count + 1);
                }
            }
        }

        int ans = min == Integer.MAX_VALUE ? -1 : min;
        memo.put(amount, ans);
        return ans;
    }
}

TC: O(amount * n) SC: O(amount)

[LannyX]

思路

背包

代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        //给0占位
        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 && dp[i - coin] != amount + 1){
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        if(dp[amount] == amount + 1){
            dp[amount] = -1;
        }
        return dp[amount];
    }
}

复杂度分析

• 时间复杂度：O(nm)
• 空间复杂度：O(m)

[hdyhdy]

func coinChange(coins []int, amount int) int {
    if amount < 1 && len(coins) < 1 {
        return -1
    }
    memo := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
        memo[i] = math.MaxInt32
        for _, c := range coins {
            if i >= c && memo[i] > memo[i-c]+1 {
                memo[i] = memo[i-c] + 1
            }
        }
    }
    if memo[amount] == math.MaxInt32 {
        return -1
    }

    return memo[amount]
}

[alongchong]

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

[wangzehan123]

代码

• 语言支持：Java

Java Code:

public class Solution {
    public int coinChange(int[] A, int M) {
        int[] f = new int[M + 1];
        int n = A.length;

        f[0] = 0;
        int i, j;
        for (i = 1; i <= M; ++i) {
            f[i] = -1;
            for (j = 0; j < n; ++j) {
                if (i >= A[j] && f[i - A[j]] != -1) {
                    if (f[i] == -1 || f[i - A[j]] + 1 < f[i]) {
                        f[i] = f[i - A[j]] + 1;
                    }
                }
            }
        }

        return f[M];
    }
}

[ZJP1483469269]

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

        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1 

[zhangzz2015]

思路

• 标准DP方法，建立dp[i][j] 位使用[0 i] 种硬币，凑成number 为 j 最少硬币数。dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]]+1) 当 j -coins[i]>=0时候，可使用coins[i] ，否则不用coins[i]。时间复杂度为O(nm)，空间复杂度为O(nm)，可优化空间复杂度。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {

        ///   dp[i][j]  =   min(dp[i-1][j],  dp[i][j-coins[i]]+1) 
        vector<vector<int>> dp(coins.size()+1, vector<int>(amount+1, 0 )); 

        for(int i=0; i<=coins.size(); i++)
        {
            for(int j=0; j<=amount; j++)
            {
                if(j==0)
                {
                    dp[i][j] = 0; 
                }
                else if(i==0)
                {
                    dp[i][j] =INT_MAX; 
                }
                else
                {
                    if(j-coins[i-1]>=0)
                    {
                        dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i-1]]==INT_MAX? INT_MAX: dp[i][j-coins[i-1]]+1); 
                    }
                    else
                        dp[i][j] = dp[i-1][j]; 
                }
            }
        }

        return dp[coins.size()][amount]==INT_MAX? - 1: dp[coins.size()][amount]; 

    }
};

[didiyang4759]

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

[zol013]

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

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

        '''
        @lru_cache(amount)
        def dp(remain):
            if remain < 0:
                return -1
            if remain == 0:
                return 0
            mini = float('inf')
            for coin in coins:
                res = dp(remain - coin)
                if res >= 0:
                    mini = min(mini, res + 1)

            return mini if mini != float('inf') else -1

        return dp(amount)
        '''

        q = deque([(amount, 0)])
        seen = set([amount])

        while q:
            remain, num_coins = q.popleft()
            if remain == 0:
                return num_coins
            for coin in coins:
                if remain - coin >= 0 and remain - coin not in seen:
                    q.append((remain - coin, num_coins + 1))
                    seen.add(remain - coin)

        return -1

[watchpoints]

class Solution {

public:
    int coinChange(vector<int>& coins, int amount) {

     sort(coins.begin(),coins.end(),greater<int>());//对金额进行排序,优先寻找最短路径 进行剪枝

     int res=INT_MAX;//依然是遍历全部路径，选择最短的一个。

    //递归回溯
    dfs(coins,amount,0,0,res); //依然全部遍历
    //如果没有任何一种硬币组合能组成总金额，返回 -1。
    return res ==INT_MAX?-1:res;

    }
    //used 硬币数量虽然无限，但是种类是有限的.
    void dfs(vector<int> &coins,int amount,int used,int total,int& res)
    {
        if (amount < 0)
        {
            return ;//剪枝

        }

        if (amount == 0)
        { 
            res =min(res,total); 
           return ;//叶子节点
        }

        //遗忘了 ！！！！！
        if (used >= coins.size())
        {
            return ;// coins = [2], amount = 3  3=1*2+(失败)) 3=0*2+（失败）
        }
        //每种硬币的数量是无限的 
        int count =amount/coins[used];
        //11 = 5 + 5 + 1
        //优化：如果比res还大，没必要递归了
        for (int i=count;i >= 0 && (total+i) < res ;i--)
        {
            int left = amount-i*coins[used]; //剩余金额 , i硬币个数，用乘法代替减法。11-5 ,6-5 2次递归

            dfs(coins,left,used+1,total+i,res); //必须全部尝试，因为是否组合成功不清楚。

            //代码要检查 检查 检查。
        }

    }

};

[demo410]

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

[Menglin-l]

approach: dynamic programming

---

code:

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; 
            for (int j = 0; j < coins.length; j++) {
                int remain = i - coins[j];
                if (remain >= 0) {
                    dp[i] = Math.min(dp[i], dp[remain] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

---

complexity:

Time: O(amount * N)

Space: O(amount)

[1149004121]

322. 零钱兑换

思路

背包问题。

代码

var coinChange = function(coins, amount) {
    const n = coins.length;
    let dp = new Array(1 + amount).fill(1 + amount);
    dp[0] = 0;

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

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

复杂度分析

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

[spacker-343]

思路

完全背包问题，n刷了

代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int len = coins.length;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int j = 0; j < len; j++) {
            for (int i = coins[j]; i <= amount; i++) {
                if (dp[i - coins[j]] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        if (dp[amount] == Integer.MAX_VALUE) {
            return -1;
        }
        return dp[amount];
    }
}

复杂度

时间复杂度: O(n * K) 空间复杂度: O(n)

[Toms-BigData]

func coinChange(coins []int, amount int) int { dp:=make([]float64, amount+1) for i := 1; i < len(dp); i++ { dp[i] = math.MaxFloat64 } for i := 0; i < len(coins); i++ { for j := coins[i]; j < amount+1; j++ { if dp[j] > dp[j-coins[i]]+1 { dp[j] = dp[j-coins[i]]+1 } } } if dp[amount] == math.MaxFloat64{ return -1 }else { return int(dp[amount]) } }

[Myleswork]

class Solution { public: vector cur; int minlen; void dfs(vector& coins,int amount,int& sum){ if(sum==amount){ minlen = min(minlen,(int)cur.size()); return; } for(int i = 0;i<coins.size()&&sum<amount&&coins[i]<=amount;i++){ sum+=coins[i]; cur.push_back(coins[i]); dfs(coins,amount,sum); sum-=coins[i]; cur.pop_back(); } } int coinChange(vector& coins, int amount) { int sum = 0; minlen = INT_MAX; dfs(coins,amount,sum); return minlen==INT_MAX?-1:minlen; } }; 会超时

[liuzekuan]

思路

• 动态规划

  代码

• 语言支持：Java

Java Code:

class Solution {
    public int coinChange(int[] coins, int amount) {
        //定义数组，表示金额从0到amount对应的最少硬币个数
        int[] dp = new int[amount + 1];
        //将数组元素填充为大于最大硬币个数的值
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        //控制总金额
        for (int i = 1; i <= amount; i++) {
            //控制硬币面额
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    //找出总金额减去当前硬币面额后对应的最少硬币个数
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

复杂度分析

令 n 为数组长度。

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

[shamworld]

var coinChange = function(coins, amount) { if(amount===0)return 0; //初始化长度为amount+1，值为无穷大的数组 let dp = Array(amount+1).fill(Infinity); dp[0] = 0; for(let i = 0; i < dp.length; i++){ for(let j = 0; j < coins.length; j++ ){ // 如果差值小于零 if(i - coins[j] < 0) continue; // 每一个金额最低需要几个硬币 dp[i] = Math.min(dp[i],dp[i-coins[j]]+1); } } if(dp[amount]===Infinity) return -1; return dp[amount]; };

[Richard-LYF]

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

    dp = [amount + 1] * amount + [amount + 1]

    dp[0] = 0

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

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

on amout oamount

[declan92]

思路

1. dp[i][j]表示取第i个硬币总和为j的最少硬币个数;
2. dp[i][j] = min(dp[i][j-coins[i]]+1,dp[i-1][j]);
3. if(j%coins[0] == 0) dp[0][j] = j/coins[0];
4. 嵌套循环遍历 步骤
5. 特殊情况amount = 0,返回0;
6. 定义dp数组int[coins.length][amount+1];
7. dp数组初始值给最大值amount+1,并计算dp[0][j]表示取第0个元素(边界);
8. 双循环,状态转移方程;
   1. j>=coins[i],dp[i][j] = Math.min(dp[i][j-coins[i]]+1,dp[i-1][j]);
   2. 否则dp[i][j] = dp[i-1][j];
9. 返回dp[coins.length-1]amount; java code

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

   时间:$O(nm)$ 空间:$O(nm)$

[15691894985]

**【Day 63】

货物量无限制，完全背包问题 dp[j] 代表 j金额数时的硬币数

凑成总金额的最小硬币数 dp初始化为最大max_value dp=[0] 在i物品选完后 该物品还可以接着选，并不会移动到下一个物品

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount+1]*(amount+1)
        dp[0] = 0
        for num in coins:
            for j in range(1,amount+1):
                if j >= num: 
                    dp[j] = min(dp[j],dp[j-num]+ 1) #状态转移方程
        return -1 if dp[amount] == amount+1  else dp[amount]

时间复杂度：(num*amount)

空间复杂度：O( amount)

[callmeerika]

思路

动态规划

代码

var coinChange = function(coins, amount) {
    const n = coins.length;
    const max = amount + 1;
    const dp = new Array(max).fill(max)
    dp[0] = 0;
    for(let i = 1;i <= amount;i++) {
        for(let j = 0;j < n;j++) {
            const num = coins[j]
            if(num <= i) {
                dp[i] = Math.min(dp[i], dp[i-num] + 1)
            } 
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
};

复杂度

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

[fornobugworld]

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

dp[j] :凑成整数j的最少硬币数目

    #dp[0] = 0
    #dp[j] = min(dp[j-coins[i]]+1) ,i=0~len(coins)
    dp = [20000] * (amount + 1)
    dp[0] = 0
    for i  in range(1,amount+1):
        for j in coins:
            if amount <j:
                continue
            dp[i] = min(dp[i],dp[i-j]+1)
    return dp[amount] if dp[amount]<20000 else -1

[xinhaoyi]

//记忆化+递归 class Solution { int[] memo; public int coinChange(int[] coins, int amount) { if(coins.length == 0){ return -1; } memo = new int[amount];

    return findWay(coins,amount);
}
// memo[n] 表示钱币n可以被换取的最少的硬币数，不能换取就为-1
// findWay函数的目的是为了找到 amount数量的零钱可以兑换的最少硬币数量，返回其值int
public int findWay(int[] coins,int amount){
    if(amount < 0){
        return -1;
    }
    if(amount == 0){
        return 0;
    }
    // 记忆化的处理，memo[n]用赋予了值，就不用继续下面的循环
    // 直接的返回memo[n] 的最优值
    if(memo[amount-1] != 0){
        return memo[amount-1];
    }
    int min = Integer.MAX_VALUE;
    for(int i = 0;i < coins.length;i++){
        int res = findWay(coins,amount-coins[i]);
        if(res >= 0 && res < min){
            min = res + 1; // 加1，是为了加上得到res结果的那个步骤中，兑换的一个硬币
        }
    }
    memo[amount-1] = (min == Integer.MAX_VALUE ? -1 : min);
    return memo[amount-1];
}

}

[GaoMinghao]

思路

完全背包问题

代码

public int coinChange(int[] coins, int amount) {
    if (coins == null || coins.length == 0 || amount <= 0)
        return 0;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

[ozhfo]

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; 
            for (int j = 0; j < coins.length; j++) {
                int remain = i - coins[j];
                if (remain >= 0) {
                    dp[i] = Math.min(dp[i], dp[remain] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

[CodingProgrammer]

思路

完全背包

代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0) {
            throw new IllegalArgumentException();
        }

        if (amount == 0) return 0;
        // dp[i] 表示凑成总额为 i 最少需要的硬币数量
        // dp[i] = Math.min(dp[i], dp[i - coin])
        int[] dp = new int[amount + 1]; // 初始化一个不可能的最大值
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int coin : coins) {
            for (int j = 0; j <= amount; j++) {
                if (j >= coin) {
                    dp[j] = Math.min(dp[j], dp[j - coin] + 1);
                }
            }
        }

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

    }
}

复杂度

• 时间复杂度：O(N * M) N 为硬币数量，M为凑成的金额数
• 空间复杂度：O(M)

[hx-code]

dp = [amount + 1] * amount + [amount + 1]

dp[0] = 0

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

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

[zzzpppy]

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

[charlestang]

思路

动态规划

设 dp[i] 表示，能凑出金额 i 的最少硬币枚数。

对每一个硬币的面额 c， dp[i] = min(dp[i - c] + 1)

代码

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

        for i in range(1, amount + 1):
            for c in coins:
                if i >= c and dp[i - c] != -1:
                    if dp[i] == -1:
                        dp[i] = dp[i - c] + 1
                    else:
                        dp[i] = min(dp[i], dp[i - c] + 1)

        return dp[amount]

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

空间复杂度 O(amount)

[machuangmr]

代码

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

        // memo[n] 表示凑够面值为n需要的硬币个数
        int[] memo = new int[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] 有两种实现的方式
                    // 1、不包含当前的coins[i]，那么需要的硬币数量就是 memo[i - coins[j]] +1
                    // 2、另一种就是包含当前的coins[j], 
                    memo[i]  = Math.min(memo[i], memo[i - coins[j]] +1);
                }
            }
        }
        return memo[amount] == amount + 1? -1: memo[amount];
    }
}

[CodeFarmersWorld]

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

[for123s]

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

[Jay214]

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    const maxCount = amount + 1
    const dp = new Array(maxCount).fill(maxCount)
    dp[0] = 0
    for (let i = 1; i <= maxCount; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (coins[j] <= i) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
            }
        }
    }
    return dp[amount] >= maxCount ? -1 : dp[amount]
};

[ChenJingjing85]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [10001 for _ in range(amount+1)] #凑出金额i的最少硬币数,初始化为一个极大值
        dp[0] = 0
        for j in range(1, amount+1):
            for c in coins:
                if j < c:
                    continue
                dp[j] = min(dp[j], dp[j-c]+1)
        return dp[amount] if dp[amount] != 10001 else -1

[taojin1992]

class Solution {
    // time: O(coins.length * amount)
    // space: O(amount)
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int i = 0; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin && dp[i - coin] != -1) {
                    if (dp[i] == -1) {
                        dp[i] = 1 + dp[i - coin];
                    } else {
                        dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
                    }
                }
            }
        }
        return dp[amount];
    }
}