【Day 63 】2023-04-17 - 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

[lp1506947671]

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]

复杂度分析

令 N 为物品个数即硬币种类， amount 为总金额也即背包大小。

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

[LIMBO42]

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

[RestlessBreeze]

code

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

[Meisgithub]

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

[csthaha]

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

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

[Diana21170648]

思路

动态规划，背包，取最小值，则dp、初始化为max_value,dp[0]=0

class Solution:
    def coinschange(self,coins,amount)->int:
        dp = [amount + 1] * (amount + 1)#取左不取右，amount+1本来就不存在
        dp[0] = 0
        # 不满足组合，返回-1
        if dp[amount]==amount+1 or dp[amount]:
            return -1

        for i in range(1,amount+1):
            for j in range(coins):
                if i>=coins:
                    dp[i]=min(dp[i],dp[i-j]+1)#总数大于面值，更新最小硬币的值，使得用的硬币数量最少
                    return dp[amount]#满足最小硬币个数，返回硬币个数

**复杂度分析**
- 时间复杂度：O(N*amount)，其中 N 为硬币种类。
- 空间复杂度：O(amount)

[zhangyu1131]

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // dp[i][j]表示前i种零钱兑换成面额j的最小种数
        // 滚动数组优化
        int n = coins.size();
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= amount; ++j)
            {
                if (j >= coins[i - 1]) //可以选
                {
                    // 可以选但不一定非要选，还是要比较
                    dp[j] = std::min(dp[j], dp[j - coins[i - 1]] + 1);
                }
                else
                {
                    // 不可以选
                    dp[j] = dp[j];
                }
            }
        }

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

[GuitarYs]

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

[jackgaoyuan]

func coinChange(coins []int, amount int) int {
    if amount == 0 {
        return 0
    }
    if len(coins) == 0 && amount > 0 {
        return -1
    }
    resCache := make(map[int]int)
    return findFewestNum(coins, 0, resCache, amount)
}

/*
当前curTotal情况下，满足条件的最少硬币数
*params: curTotal就是当前的状态，因为每个面值的硬币无限多，因此硬币使用情况不影响当前的状态
*params: resCache: { key: curTotal, value: minNum }
*/
func findFewestNum(coins []int, curTotal int, resCache map[int]int, amount int) (res int) {
    if value, ok := resCache[curTotal]; ok {
        return value
    }
    if curTotal == amount {
        return 0
    }
    if curTotal > amount {
        return -1
    }
    defer func(){
        if _, ok := resCache[curTotal]; !ok {
            resCache[curTotal] = res
        }
    }()
    minNum := math.MaxInt
    for _, value := range coins {
        num := findFewestNum(coins, curTotal + value, resCache, amount)
        if num != -1 && num < minNum {
            minNum = num
        }
    }
    if minNum == math.MaxInt {
        return -1
    }
    return minNum + 1
}

[FireHaoSky]

思路：动态规划， 状态转移F(s) = min(c in coins)(F(s-c)) + 1

代码：python

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

        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

复杂度分析：

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

[harperz24]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [sys.maxsize] * (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] != sys.maxsize else -1

[SoSo1105]

class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [sys.maxsize] * (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] != sys.maxsize else -1

[kofzhang]

思路

动态规划 遍历钱数，当前最小值取 当前值和从前面对应钱数过来，取最小值。dp[i]=min(dp[i],dp[i-coin]+1)

复杂度

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

代码

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

[wangqianqian202301]

class Solution(object):
    def coinChange(self, coins, amount):
        def dp_solver(index, target, dp):
            if index == 0:
                if target % coins[0] == 0:
                    return target / coins[0]

                return 1e9

            if dp.get((index,target)):
                return dp.get((index,target))

            not_take = dp_solver(index -1, target, dp)
            take = sys.maxsize

            if coins[index] <= target:
                take = 1 + dp_solver(index, target - coins[index], dp)

            dp[(index, target)] = min(take, not_take)
            return dp[(index, target)]

        ans =  dp_solver(len(coins)-1, amount, {})
        if ans >= 1e9:
            return -1
        return ans

[bookyue]

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

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

[JingYuZhou123]

/**
 * @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];
}

[NorthSeacoder]

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    const sum = coins.reduce((acc, cur) => acc + cur, 0);
    coins.sort((a, b) => a - b);
    //dp[j]凑成 j 的最小硬币个数
    const dp = new Array(amount + 1).fill(Infinity);
    //dp[j] = Math.min(dp[j-coins[i]],dp[j]);
    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], dp[j - coins[i]] + 1);
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
};

[aswrise]

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

[JasonQiu]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [(amount + 1) for i in range(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)
        return dp[amount] if dp[amount] < amount + 1 else -1

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

[X1AOX1A]

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]

[jiujingxukong]

思路

动态规划。

1. base case:amount===0时，返回0
2. amount的变化可以分解成子问题
3. amount的变化是由不同的硬币组成而来的
4. dp 函数/数组的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。

此外，要注意剪枝（按照树的结构想象需要的运算），这就需要新建一个数组来存放从0到越来越大的amount需要的结果数。

js代码

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  let memo = new Array(amount + 1).fill(-2);
  return dp(coins, amount);

  function dp(coins, amount) {
    if (amount === 0) return 0;
    if (amount < 0) return -1;
    if (memo[amount] !== -2) {
      return memo[amount];
    }

    let res = Number.MAX_SAFE_INTEGER;
    for (let coin of coins) {
      let subProblem = dp(coins, amount - coin);
      if (subProblem === -1) continue;
      res = Math.min(res, subProblem + 1);
    }
    memo[amount] = res === Number.MAX_SAFE_INTEGER ? -1 : res;
    return memo[amount];
  }
};

复杂度

令 N 为物品个数即硬币种类， amount 为总金额也即背包大小。

• TC:O（N*amount）
• SC:O(amount)

[sye9286]

代码

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
  let dp = new Array( amount + 1 ).fill( Infinity );
  dp[0] = 0;

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

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

复杂度分析

• 时间复杂度：O(N * amount) N 为面额数量
• 空间复杂度：O(amount)

[bingzxy]

思路

动态规划，定义状态方程 dp[i] 表示为达成金额 i 的最小硬币数据，转移方程 dp[i] = Math.min(dp[i - j], dp[i]) , j ∈ coins, 当 i - j >= 0

代码

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

        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;
        }

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

复杂度分析

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

[Lydia61]

322. 零钱兑换

思路

动态规划，完全背包

代码

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 

复杂度分析

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

[kangliqi1]

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

}

[KrabbeJing]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dump = [float("inf")] * (amount + 1)
        dump[0] = 0
        for i in range(1, amount+1):
            for coin in coins:
                if i>=coin:
                    dump[i] = min(dump[i], dump[i-coin]+1)
        if dump[amount] == float("inf"):
            return -1
        else:
            return dump[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];
    }
};

[joemonkeylee]

思路

dp

代码

        public int CoinChange(int[] coins, int amount)
        {
            int[] dp = new int[amount + 1];
            int max = Int;

            for (int j = 0; j < dp.Length; j++)
                dp[j] = 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];
        }

[yingchehu]

class Solution:
    def coinChange(self, coins, amount):
        dp = [amount + 1] * (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)
        return -1 if dp[amount] == amount + 1 else dp[amount]

[CruiseYuGH]

''' 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] '''

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

复杂度分析

• 时间复杂度：O(Sn)，其中 S 是金额，n是面额数。
• 空间复杂度：O(n)

[aoxiangw]

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 c in coins:
                if i - c >= 0:
                    dp[i] = min(dp[i], 1 + dp[i-c])
        return dp[amount] if dp[amount] != amount + 1 else -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];
    }
};

[Zoeyzyzyzy]

class Solution {
    // dp[i]: 最小需要dp[i]个数来表示i，
    // dp[i] = Math.min(dp[i],dp[i - j] + 1) j为数组中的所有数
    // 初始化: dp[i] = amout + 1;
    // 顺序：从左到右
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 0; i <= amount; i++) {
            dp[i] = amount + 1;
        }
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == amount + 1 ? -1:dp[amount];
    }
}

[chanceyliu]

代码

function coinChange(coins: number[], amount: number): number {
  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];
}

复杂度分析

• 时间复杂度：O(amount * n) n 为 coins 数组长度
• 空间复杂度：O(amount)