零钱兑换：
为什么完全背包要正序遍历，dp 代表什么

贪心的直觉，为什么在此处失效？

给定一个整数数组 coins 表示不同面额的硬币，以及一个整数 amount 表示总金额。计算凑成总金额所需的最少硬币数。如果无法凑出，则返回 -1。你可以认为每种硬币的数量是无限的。

生活中的直觉常常告诉我们：尽可能先找最大面额的钱。例如面额 [1, 2, 5] 凑 11 元，先拿 5，再拿 5，最后拿 1，共 3 枚，确实是最优解。但这仅仅是因为特定面额恰好满足贪心选择性质。

逐面额填表，步进推演最优转移。

观察 dp[j] 如何随着硬币面额逐步被测试与更新。高亮方块展示了当前计算的目标金额 j 与来源前置金额 j - coin 之间的差额对比。

三个关键细节：为什么正序，怎么判负？

1. 01

   完全背包必须“从小到大（正序）”遍历

   在 0/1 背包（如 LeetCode 416）中，每个物品只能用一次，所以内层循环必须从大到小逆序，确保计算 dp[j] 时用到的 dp[j - weight] 尚未包含当前物品；而零钱兑换硬币可以无限次重复使用，所以内层循环必须从小到大正序推进，使得前面刚使用过的硬币在后续更大金额时能够自然复用。

2. 02

   初始化不能只设 dp[0]，其余要设为极大值

   因为求的是最小值（min），如果数组默认全为 0，那么后续任何比较都会直接被 0 覆盖，完全无法得到正确答案。因此除 dp[0] = 0 外，dp[1..amount] 必须初始为一个不可能被超越的上限，如 amount + 1。

3. 03

   用 dp[amount] == amount + 1 判定不可达

   所有硬币遍历完毕后，检查目标金额位。若 dp[amount] 依然保持初始的极大值，证明没有任何面额组合能够拼出该金额，严格返回 -1。

真实 C 语言实现节选

选自 CSP 练习记录中已通过评测的源码。纯静态数组，无动态堆分配，运行极速。

int coinChange(int *coins, int coinsSize, int amount) {
    int dp[MAXN];
    for (int i = 0; i <= amount; i++) {
        dp[i] = amount + 1; // 初始化为不可能达到的极大值
    }
    dp[0] = 0; // 凑出 0 元所需硬币为 0

    for (int i = 0; i < coinsSize; i++) {
        int num = coins[i];
        for (int j = num; j <= amount; j++) { // 正序遍历：完全背包允许重复使用
            if (dp[j - num] + 1 < dp[j]) {
                dp[j] = dp[j - num] + 1;
            }
        }
    }

    if (dp[amount] == amount + 1) {
        return -1; // 无法拼出该金额
    }
    return dp[amount];
}

复杂度与空间压缩