题目

思路

一句话：把“凑 amount 最少几枚”拆成“最后一次选哪枚硬币”，用 dp[a] 记录凑金额 a 的最少枚数，从小到大推。

先想最直白的贪心：每次都尽量用最大面额。它对 [1,2,5], 11 碰巧成立（5+5+1），但换成 [1,3,4], 6 就翻车：贪心先拿 4，剩下 2 要两个 1，共 3 枚；最优其实是 3+3，只要 2 枚。

再想枚举所有组合：每种硬币可不限次地选，搜索树分支极多，而且“凑 3 需要几枚”这类子问题会被反复重算，是指数级时间，不可接受。

关键观察：这个问题有最优子结构。如果最后一次选的硬币面额是 c，那么凑 amount 的最少枚数就是 1 + 凑(amount - c) 的最少枚数；对所有可选 c 取最小即可。于是得到转移：

dp[a] = min(1 + dp[a - c])，其中 c 遍历所有 c ≤ a 的硬币。

边界 dp[0] = 0（凑 0 元不需要硬币），其余先设成“无穷大”表示暂时凑不出。每个子状态只算一次、每个状态尝试 n 种硬币，复杂度 O(n·amount)，完全可接受。

解法

用一维数组 dp[0..amount]：dp[a] 表示凑出 a 的最少硬币数。初始 dp[0] = 0，其余为 amount + 1（当作无穷大哨兵），然后按金额从小到大填充。

1. 令 dp[0] = 0，其余全部为 amount + 1。
2. 对每个金额 a = 1..amount：枚举每种硬币 c，若 c ≤ a，用 1 + dp[a-c] 更新 dp[a]。
3. 最终 dp[amount] 仍是哨兵就返回 -1，否则返回 dp[amount]。