零钱兑换问题如何用动态规划求解？（完全背包，LeetCode 322）

简化版

给不同面额的硬币（每种无限个）和目标金额 amount，求凑出该金额所需的最少硬币数，凑不出返回 -1。这是完全背包求最小值：dp[j] = 凑出金额 j 的最少硬币数，转移 dp[j] = min(dp[j], dp[j-coin] + 1)。因为硬币能重复用，一维遍历容量要正序。初始化 dp[0]=0、其余为「无穷大」，最后若 dp[amount] 仍是无穷大说明凑不出。

详细版

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);     // 用 amount+1 当「无穷大」(硬币数不可能超过 amount)
    dp[0] = 0;                        // 凑 0 元需要 0 枚
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {     // 容量正序：硬币可重复用
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];  // 仍是「无穷大」→ 凑不出
}

状态：dp[j] = 凑出金额 j 所需的最少硬币数。
转移方程：dp[j] = min(dp[j], dp[j-coin] + 1)（用一枚 coin + 凑出 j-coin 的最少数）。
正序遍历容量：因为硬币可无限次用（完全背包）。
初始化：dp[0]=0；其余置一个够大的值（amount+1）代表暂时无解。
复杂度：O(n·amount) 时间、O(amount) 空间。

完整版教学

一、问题：硬币无限，凑 amount 的最少个数

零钱兑换：硬币面额 coins = [1,2,5]，目标 amount = 11，最少用 3 枚（5+5+1）。特点是每种硬币可以用无限次——这正是完全背包的标志（0-1 背包每件只用一次）。目标是「最少硬币数」，属于背包求最优值的一种。

二、完全背包模型：状态与转移

定义状态：dp[j] = 「凑出金额 j 所需的最少硬币数」。目标求 dp[amount]。

转移方程——盯住「凑金额 j 的最后一枚硬币是哪种」。若最后放的是面额 coin 的硬币，那么剩下的 j-coin 得用最少的硬币凑好，再加这一枚：

dp[j] = min over 所有 coin ( dp[j-coin] + 1 )

写进代码就是遍历每种 coin，用 dp[j] = min(dp[j], dp[j-coin] + 1) 不断更新。

三、正序遍历：为什么完全背包正序（可重复用）

一维数组下，遍历容量的方向决定「每种硬币能用几次」（和 0-1 背包倒序恰好相反）：

正序（j 从 coin 到 amount）：算 dp[j] 时用到的 dp[j-coin]，在本轮已经可能被同一种硬币更新过——也就是说 dp[j-coin] 里可以已经包含了若干枚 coin，再 +1 就是又用了一枚同种硬币。正是这个「本轮已更新」的特性，让同一种硬币被重复使用，符合完全背包。
若像 0-1 背包那样倒序，dp[j-coin] 会停留在「还没用这种硬币」的状态，每种硬币最多用一次——那就不是零钱兑换了。

对照记忆：完全背包（物品无限）→ 容量正序；0-1 背包（物品一次）→ 容量倒序。 零钱兑换的硬币无限，所以正序。

四、初始化与无解判断

dp[0] = 0：凑 0 元不需要硬币，是递推的基石。
其余 dp[j] 初始化为一个「无穷大」：这里用 amount + 1。因为凑出金额 j 最多也就用 j 枚 1 元硬币，硬币数绝不会超过 amount，所以 amount+1 是个安全的「不可能达到」的哨兵值。
无解判断：跑完后如果 dp[amount] 还是那个哨兵值（> amount），说明这些面额根本凑不出 amount，返回 -1。

易错点：别用 Integer.MAX_VALUE 当无穷大后直接 +1——会整型溢出变负数，导致 min 取错。用 amount+1 这种「足够大又不会溢出」的值最稳妥。

五、对比：求最少个数 vs 求方案数，遍历顺序的讲究

零钱兑换有个孪生题 零钱兑换 II（LeetCode 518）：求凑出 amount 的组合方案数，两题遍历顺序的要求不同，是高频陷阱：

求最少硬币数（本题）：转移是取 min，两层循环谁在外都对——因为 min 与顺序无关。
求组合方案数（零钱 II）：必须硬币在外层、金额在内层。这样每种硬币只在「上一枚同种或不同种」基础上累加，得到的是组合数（不区分顺序，1+2 和 2+1 算一种）。
若求排列方案数（顺序不同算不同）：则要金额在外层、硬币在内层。

一句话：求方案数时，「物品外层」得组合数、「容量外层」得排列数；求最优值（min/max）则两层顺序都行。 这个区别几乎每次考背包都会问。

六、状态语义、转移来源与遍历顺序

本题状态的完整含义是：dp[x] 表示凑出金额 x 的最少硬币数，当前硬币 c 可从已可达的 dp[x-c] 转移。

转移过程是：完全背包一维实现对每枚硬币让 x 从 c 正序到 amount：dp[x]=min(dp[x],dp[x-c]+1)。写代码前应逐个解释转移候选对应题目中的哪种最后选择，并确认这些候选互斥且覆盖全部可能。

定义状态：它概括哪段输入、处于什么决策阶段
列出选择：当前答案的最后一步有哪些来源
写出转移：由已计算的前驱组合当前答案
确定顺序：使用前驱之前不能覆盖它

数字推演：coins=[1,2,5], amount=11，处理 5 后由 dp[6]+1 得 dp[11]=3，对应 5+5+1。

记忆钩子：DP 最容易错的不是 max/min，而是状态少记了信息或一维压缩后读到了本轮新值。

七、初始化、空间压缩与适用边界

实现边界是：初值用 amount+1 或安全无穷，转移前避免 INF+1；硬币须为正；求组合数与求排列数的外内循环顺序不同。

核对项	本题答案
复杂度	O(amount×硬币种数) 时间，O(amount) 空间
基本状态	必须能直接解释为规模 0 或最小输入的真实含义
遍历顺序	由转移依赖决定，不能为了习惯随意正序/倒序
空间压缩	仅在被覆盖状态之后不再需要时安全
结果位置	可能是最后状态、全局最大值或多个终态的聚合

测试应覆盖空/最小输入、不可达状态、全零或负值、答案刚好发生在边界，以及会区分正序与倒序的样例。若需要恢复方案，不能只保留压缩后的数值，还要记录前驱或保留完整状态表。

八、常见误区与追问

误区：完全背包容量也应倒序。 正序才能让本轮刚更新状态再次使用同一硬币。
误区：dp[0] 应初始化为无穷。 凑出 0 元需要 0 枚，是所有转移的起点。
误区：最少硬币和方案数遍历完全相同。 状态聚合不同，方案计数的物品/容量顺序还决定组合或排列。
追问：为什么 INF 常设 amount+1？ 最多使用 amount 枚面值 1；该值足够表示不可达且加一安全。
追问：硬币含 0 会怎样？ 状态不能推进且“无限使用 0”语义异常，应禁止。
追问：如何恢复具体硬币？ 额外记录每个金额最后选择的硬币或前驱金额。

九、加强记忆

零钱兑换 = 完全背包求最小值：dp[j] = 凑金额 j 的最少硬币数，dp[j]=min(dp[j], dp[j-coin]+1)，硬币无限用所以容量正序遍历（对比 0-1 背包倒序）。初始化 dp[0]=0、其余置 amount+1 当无穷大（别用 MAX_VALUE 防 +1 溢出），跑完 dp[amount]>amount 则返回 -1。孪生题「求方案数」讲究遍历顺序：物品外层=组合数、容量外层=排列数，求 min/max 则两层顺序都可。

简化版

详细版