Coin Change（零钱兑换）

题目 / Problem

中文： 给定一个整数数组 coins，表示不同面额的硬币；另给一个整数 amount，表示需要凑出的总金额。

返回凑成该金额所需的最少硬币数量。如果任何硬币组合都无法凑出该金额，返回 -1。

可以假设每种面额的硬币都有无限枚。

English: You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins needed to make up that amount. If the amount cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

示例 / Examples

Example 1

Input:  coins = [1,2,5], amount = 11
Output: 3

解释 / Explanation:
11 = 5 + 5 + 1，共使用 3 枚硬币。
11 = 5 + 5 + 1, using 3 coins.

Example 2

Input:  coins = [2], amount = 3
Output: -1

无论使用多少枚面额为 2 的硬币，都无法得到奇数金额 3。
No number of denomination-2 coins can produce the odd amount 3.

Example 3

Input:  coins = [1], amount = 0
Output: 0

凑出金额 0 不需要使用任何硬币。
No coins are needed to make amount 0.

约束 / Constraints

1 <= coins.length <= 12
1 <= coins[i] <= 2³¹ - 1
0 <= amount <= 10⁴

解题思路：动态规划 / Approach: Dynamic Programming

定义：
Define:

dp[value] = 凑出金额 value 所需的最少硬币数
dp[value] = minimum coins needed to make value

初始状态 / Base Case

dp[0] = 0

凑出金额 0 不需要硬币。其他金额在计算前都标记为 Infinity，表示暂时无法凑出。
No coin is needed for amount 0. Initialize every other amount to Infinity, meaning it is currently unreachable.

假设最后使用的硬币面额是 coin。如果 coin <= value，那么在凑出 value - coin 的最优方案后再添加一枚该硬币，就能凑出 value：
Suppose the final coin has denomination coin. If coin <= value, append one such coin to an optimal solution for value - coin:

dp[value] = min(dp[value], dp[value - coin] + 1)

枚举所有可用面额，取硬币数量最少的方案。
Try every usable denomination and keep the solution using the fewest coins.

因为 dp[value] 只依赖更小的金额，所以按照金额从 1 到 amount 计算即可。
Because dp[value] depends only on smaller amounts, calculate values from 1 through amount.

JavaScript 实现 / JavaScript Implementation

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

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

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

面额可能远大于 amount，但 coin <= value 会安全地跳过这些硬币。
A denomination may be much larger than amount, but coin <= value safely skips it.

执行过程 / Walkthrough

以 coins = [1,2,5]、amount = 11 为例：
For coins = [1,2,5] and amount = 11:

金额 / `value`	最优组合示例 / Example Optimal Combination	`dp[value]`
0	不使用硬币 / No coins	0
1	`1`	1
2	`2`	1
3	`2 + 1`	2
4	`2 + 2`	2
5	`5`	1
6	`5 + 1`	2
7	`5 + 2`	2
8	`5 + 2 + 1`	3
9	`5 + 2 + 2`	3
10	`5 + 5`	2
11	`5 + 5 + 1`	3

计算 dp[11] 时：
When calculating dp[11]:

使用硬币 1 / Use coin 1: dp[10] + 1 = 2 + 1 = 3
使用硬币 2 / Use coin 2: dp[9]  + 1 = 3 + 1 = 4
使用硬币 5 / Use coin 5: dp[6]  + 1 = 2 + 1 = 3

dp[11] = min(3, 4, 3) = 3

无法凑出的金额 / Unreachable Amounts

对于 coins = [2]：
For coins = [2]:

dp[0] = 0
dp[1] = Infinity
dp[2] = 1
dp[3] = Infinity

dp[3] 最终仍为 Infinity，说明没有任何组合能够凑出金额 3，因此返回 -1。
dp[3] remains Infinity, meaning no combination can produce amount 3, so return -1.

复杂度 / Complexity

设硬币面额数量为 c，目标金额为 A。
Let c be the number of denominations and A the target amount.

时间复杂度：O(A × c)，对每个金额检查所有硬币面额。
Time: O(A × c), because every amount checks every denomination.
空间复杂度：O(A)，动态规划数组包含 amount + 1 个状态。
Space: O(A), because the DP array contains amount + 1 states.

为什么贪心不一定正确？ / Why Does Greedy Fail?

一种直觉是每次选择不超过剩余金额的最大面额，但任意硬币系统不一定满足这种贪心性质。
A tempting strategy always chooses the largest denomination not exceeding the remaining amount, but arbitrary coin systems do not necessarily support this greedy property.

例如：
For example:

coins = [1,3,4], amount = 6

贪心得到：
Greedy produces:

4 + 1 + 1 = 6  → 3 枚硬币 / 3 coins

但最优解是：
But the optimal solution is:

3 + 3 = 6      → 2 枚硬币 / 2 coins

动态规划会比较所有可能的最后一枚硬币，因此能够保证得到全局最优解。
Dynamic programming considers every possible final coin and therefore guarantees the global optimum.

自顶向下记忆化搜索 / Top-Down Memoization

也可以定义递归函数 solve(remaining)，表示凑出剩余金额所需的最少硬币数，并使用 Map 缓存结果：
A recursive function solve(remaining) can represent the minimum coins needed for the remaining amount, with a Map caching results:

function coinChangeTopDown(coins, amount) {
  const memo = new Map([[0, 0]]);

  function solve(remaining) {
    if (remaining < 0) {
      return Infinity;
    }

    if (memo.has(remaining)) {
      return memo.get(remaining);
    }

    let minimum = Infinity;

    for (const coin of coins) {
      minimum = Math.min(minimum, solve(remaining - coin) + 1);
    }

    memo.set(remaining, minimum);
    return minimum;
  }

  const answer = solve(amount);
  return answer === Infinity ? -1 : answer;
}

时间复杂度 / Time: O(A × c)
空间复杂度 / Space: O(A)，用于缓存和递归调用栈。
The memo and recursion stack use O(A) space.

由于 amount 最大为 10⁴，某些 JavaScript 环境中递归层数可能过深，因此自底向上的迭代 DP 更稳妥。
Because amount may reach 10⁴, recursion can become too deep in some JavaScript environments, making bottom-up iterative DP safer.

完全背包视角 / Unbounded Knapsack Perspective

每种硬币可以使用无限次，因此本题属于完全背包问题。状态转移中的 dp[value - coin] 可能已经使用过同一种硬币，这正符合题意。
Each denomination can be used infinitely many times, making this an unbounded knapsack problem. dp[value - coin] may already use the same coin, which is allowed.

本题求的是最少硬币数量，而不是组合数量，因此状态取最小值。
This problem asks for the minimum number of coins rather than the number of combinations, so the transition takes a minimum.

易错点 / Common Pitfalls

dp[0] 必须初始化为 0。
Initialize dp[0] to 0.
其他状态应初始化为不可达的大值，如 Infinity，不能初始化为 0。
Initialize other states to an unreachable large value such as Infinity, not 0.
目标金额为 0 时应返回 0。
Return 0 when the target amount is 0.
最终状态仍为 Infinity 时应返回 -1。
Return -1 if the final state remains Infinity.
每种硬币可以重复使用，不是每种只能选择一次的 0/1 背包。
Every coin can be reused; this is not a 0/1 knapsack where each item is selected at most once.
不能对任意硬币面额使用“每次选择最大硬币”的贪心策略。
Do not assume that repeatedly choosing the largest coin works for arbitrary denominations.

Coin Change