518.零钱兑换II

链接：518.零钱兑换II
难度：Medium
标签：数组、动态规划
简介：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

题解 1 - typescript

• 编辑时间：2021-06-10
• 执行用时：92ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：计算每种硬币的可能。

function change(amount: number, coins: number[]): number {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let i = 1; i <= amount; i++) {
      if (i >= coin) {
        dp[i] += dp[i - coin];
      }
    }
  }
  return dp[amount];
}

题解 2 - javascript

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

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

题解 3 - python

• 编辑时间：2024-03-25
• 执行用时：81ms
• 内存消耗：16.5MB
• 编程语言：python
• 解法介绍：dp记录当前金额下的能兑换的方式数。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for cur in range(coin, amount + 1):
                dp[cur] += dp[cur - coin]
        return dp[amount]