/**
 * @params {Array} coins
 * @params {Number} amount
 */
export const change = (coins, amount) => {
  // Create and initialize the storage
  const combinations = new Array(amount + 1).fill(0)
  combinations[0] = 1
  // Determine the direction of smallest sub-problem
  for (let i = 0; i < coins.length; i++) {
    // Travel and fill the combinations array
    for (let j = coins[i]; j < combinations.length; j++) {
      combinations[j] += combinations[j - coins[i]]
    }
  }
  return combinations[amount]
}
/**
 * @params {Array} coins
 * @params {Number} amount
 */
export const coinChangeMin = (coins, amount) => {
  const map = { 0: 1 }
  for (let i = 1; i <= amount; i++) {
    let min = Infinity
    for (const coin of coins) {
      if (i < coin) continue
      min = Math.min(min, 1 + map[i - coin])
    }
    map[i] = min
  }
  return map[amount] === Infinity ? -1 : map[amount] - 1
}

问题陈述

给定一个值 N，如果我们想找零 N 美分，并且我们有无限数量的 S = {S1, S2, .. , Sm} 价值的硬币，我们能用多少种方法找零？硬币的顺序无关紧要。

方法

令 dp[i] 为前缀 N[1..i] 的找零方案数量。我们的答案是 dp[N]。我们将 dp[0] 填充为 1，因为只有一种方法获得 0 个硬币（我们不选择任何硬币）。

现在让我们尝试计算任何 i 的 dp[i]。dp[0..i] 将存储从 0 到 N 的每个子问题。这就是为什么答案将是 dp[N]。首先，我们需要遍历每个硬币类型，一个一个地选择它们。然后我们遍历从我们之前选择的当前硬币到 N 美分的子问题。这就是为什么我们必须用 N 列创建 dp 表。

这是硬币找零算法的代码

    for coin_val in S:
        for i in range(coin_val, n + 1):
            dp[i] += dp[i - coin_val]

在第二次迭代中，对于可以兑换的每一美分，我们通过将第 i 列减去我们选择的硬币的值并将其加到当前列来获取它。因此 dp[i] 将存储当前子问题。

时间复杂度

在任何情况下都是 O(N * S)

空间复杂度

O(N) - 简单实现。我们只需要一个一维数组来存储答案。

示例

假设我们有 3 种硬币类型 [1,2,3]，我们想要找零 7 美分。因此我们将定义这样的表格。

[1, 0, 0, 0, 0, 0, 0, 0]

第 0 列将存储 1，因为只有一种方法获得 0 美分。

• 对于第一次迭代，我们选择一个价值为 1 的硬币。然后对于所有子问题，只有一种找零方法。对于 7 美分，唯一的方法是 {1,1,1,1,1,1,1}。在最后一次迭代中，我们的表格将类似于

[1, 1, 1, 1, 1, 1, 1, 1]

• 对于第二次迭代，我们选择一个价值为 2 的硬币。从这里开始，所有可以被 2 整除的子问题将存储另一种找零方法。因此，当迭代在第 2 列停止时，它将类似于 dp[2] += dp[0]。我们知道 dp[0] 存储的值为 1。因此，dp[2] 将存储 1 + 1 = 2 的值。从这里我们知道，对于 2 美分，有 2 种方法 {1,1} 和 {2}。此操作将继续进行。现在我们的表格将类似于

[1, 1, 2, 2, 3, 3, 4, 4]

4 种方法使用价值 1 和 2 找零 7 美分。 {{1,1,1,1,1,1,1}, {1,1,1,1,1,2}, {1,1,1,2,2}, {1,2,2,2}}

• 对于最后一次迭代（第三次迭代），我们选择一个价值为 3 的硬币。与之前一样，现在所有可以被 3 整除的列将存储另一种找零方法。最终结果将类似于

[1, 1, 2, 3, 4, 5, 7, 8]

所以最终答案是 **8**。8 种方法使用所有硬币类型找零 7 美分。 {{1,1,1,1,1,1,1}, {1,1,1,1,1,2}, {1,1,1,2,2}, {1,2,2,2}, {1,1,1,1,3}, {1,3,3}, {2,2,3}, {1,1,2,3}}

视频解释

由 Back To Back SWE 提供的找出找零的总唯一方法