322.零钱兑换

链接：322.零钱兑换
难度：Medium
标签：广度优先搜索、数组、动态规划
简介：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回  -1。

题解 1 - typescript

• 编辑时间：2021-09-13
• 执行用时：1256ms
• 内存消耗：43.6MB
• 编程语言：typescript
• 解法介绍：动态规划。

function coinChange(coins: number[], amount: number): number {
  if (amount === 0) return 0;
  coins = coins.sort((a, b) => a - b).filter(v => v <= amount);
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  coins.forEach(coin => (dp[coin] = 1));
  for (let i = 1; i <= amount; i++) {
    if (dp[i] !== Infinity) continue;
    for (const coin of coins) {
      if (i < coin) continue;
      const maxCount = ~~(i / coin);
      for (let c = maxCount; c >= 0; c--) {
        dp[i] = Math.min(dp[i], dp[i - coin * c] + c);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

题解 2 - javascript

• 编辑时间：2020-05-09
• 执行用时：80ms
• 内存消耗：41MB
• 编程语言：javascript
• 解法介绍：递推，每一项等于最小的前一项+1。

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  if (coins.length === 0) return -1;
  const minCoins = [];
  minCoins[0] = 0;
  let num, min;
  for (let i = 1; i <= amount; i++) {
    min = Infinity;
    for (const coin of coins) {
      if (i >= coin && min > (num = minCoins[i - coin])) {
        min = num;
      }
    }
    minCoins[i] = min + 1;
  }
  return minCoins[amount] === Infinity ? -1 : minCoins[amount];
};

题解 3 - javascript

• 编辑时间：2021-09-13
• 执行用时：104ms
• 内存消耗：43.5MB
• 编程语言：javascript
• 解法介绍：动态规划。

function coinChange(coins: number[], amount: number): number {
  coins.sort((a, b) => a - b);
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin > i) break;
      dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

题解 4 - python

• 编辑时间：2024-03-24
• 执行用时：803ms
• 内存消耗：16.73MB
• 编程语言：python
• 解法介绍：dp记录当前金额下的最小硬币数。

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