难 · 动态规划

凑硬币

这道题你见过一次 —— 面值 25/10/5/1，当时贪心可证最优。换一套面值，那个证明就蒸发了。而动态规划不关心拿到什么硬币：它对每个子金额都问一遍诚实的最小值。

一句话答案<code>best[0] = 0</code>；对每个金额 x 和每枚硬币 c：<code>best[x] = min(best[x], best[x-c] + 1)</code>。答案就是 <code>best[amount]</code>，一直不可达则输出 -1。

题目

输入: 第一行是 n 和 amount（1 ≤ n ≤ 10，1 ≤ amount ≤ 10000）。第二行 n 种互不相同的面值（1 ≤ c ≤ 1000），每种数量无限。

输出: 凑出 amount 所需的最少硬币数；凑不出则输出 -1。

样例:

输入输出
3 11
1 2 5		3
2 7
2 4		-1

面值 {1, 3, 4}、金额 6 时，贪心拿 4+1+1（三枚），而 3+3 只要两枚 —— 在样例上把两种都跑一遍，看看差别。表从不选「眼下最好」的硬币，它选的是「最好的结局」。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 先定义格子，再写循环

best[x] 的含义：恰好凑出 x 的最少硬币数；凑不出则为无穷大。定义定死，递推式几乎是被逼出来的 —— 凑出 x 的最优方案里最后一枚必是某枚 c，它之前是凑 x − c 的最优方案：best[x] = 各 c 中 best[x-c] + 1 的最小值。

提示 2 — 无穷大需要保镖

给不可达的金额用一个很大的 INF（比如 1000000000）—— 但转移处要设防：if (best[x-c] != INF && best[x-c] + 1 < best[x])。不设防的话，INF + 1 会混进表里，毒液蔓延到所有更大的金额。这个缺失的判断是本题最常见的 bug。

提示 3 — -1 也是表里的答案

填完表后，best[amount] 要么是真计数，要么还是 INF —— 后一种情况输出 -1。不要试图在循环途中判断「不可能」；表填完就是填完了，不可能只是某个格子始终没被改善。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int best[10005];

int main() {
    int n, amount;
    cin >> n >> amount;
    int c[10];
    for (int i = 0; i < n; i++) cin >> c[i];

    const int INF = 1000000000;
    best[0] = 0;
    for (int x = 1; x <= amount; x++) best[x] = INF;

    for (int x = 1; x <= amount; x++) {
        for (int i = 0; i < n; i++) {
            if (c[i] <= x && best[x - c[i]] != INF && best[x - c[i]] + 1 < best[x]) {
                best[x] = best[x - c[i]] + 1;
            }
        }
    }

    cout << (best[amount] == INF ? -1 : best[amount]) << endl;
    return 0;
}

这是「完全背包」最朴素的戏服，也是 最少硬币数 的直接续集 —— 同一个故事，翻过一章。值得带走的模式：贪心没有证明时，给子问题定义一张表，让转移替你做决定。同一张表加一个维度就是 0/1 背包，再往后是子集,然后是所有事。

深度解析

为什么这样做对

贪心拿最大硬币,在 {1,3,4} 上翻车 —— 所以放弃局部选择,定义 best[x] = 恰好凑出 x 的最少硬币数。任何最优支付方案的最后一枚必是某枚 c,于是 best[x] = 各硬币中 min(best[x−c] + 1)。自底向上扫 x,每个子答案在被引用时都已就绪:不需要贪心证明,因为根本没有贪心。

代价

时间 O(n × amount),空间 O(amount) —— 10 × 10000 = 10 万次转移,瞬间完成。指数级替代方案(每步试每枚硬币)会把同样的子金额重算天文数字遍。

常见错法

  • 放 INF+1 进表:转移时不设 best[x-c] != INF 的防,毒液蔓延到所有更大的金额。这是本题最常见的 bug,没有之一。
  • 忘了 best[0] = 0 —— 这个边界让「用 0 枚硬币凑 0 元」合法,所有链条都从它生长。
  • 凑不出时输出 0 而不是 -1,或在循环途中判断「不可能」:表先填完,不可能只是某个格子一直没被改善。

下一步

能成立(以及为什么)的贪心对照组是 最少硬币数;这里写的 DP 就是换装后的完全背包。加一个维度就成 0/1 背包 —— 通向一整个家族的门。

记住这两句

  • 贪心没有证明时,给子金额定义一张表,让转移替你做决定。
  • INF 是哨兵,不是数:凡碰到它的转移都要设防。
🐞 这段是错的 —— 点开,亲手让它挂一次

又是贪心 —— 凑 6 拿了 4+1+1,而 3+3 只要两枚

#include <iostream>
using namespace std;

int main() {
    int n, amount;
    cin >> n >> amount;
    int c[10];
    for (int i = 0; i < n; i++) cin >> c[i];
    int left = amount, count = 0;
    while (left > 0) {
        int take = -1;
        for (int i = 0; i < n; i++) {
            if (c[i] <= left && c[i] > take) take = c[i];  // bug: greedy
        }
        if (take == -1) { cout << -1 << endl; return 0; }
        left -= take;
        count++;
    }
    cout << count << endl;
    return 0;
}