跳至主要內容

零钱兑换——完全背包的状态转移推导与空间压缩

老张2026/4/30大约 10 分钟

零钱兑换——完全背包的状态转移推导与空间压缩

适读人群：Java后端工程师、背包DP学习者 | 阅读时长：约20分钟 | 难度：Medium

开篇故事

背包问题是DP里的大山。我2015年开始系统刷题，足足用了两个月才把背包系列理清楚。其中最让我绕弯子的，不是01背包，而是完全背包。

两者的区别就一条：01背包每件物品只能用一次，完全背包每件物品可以用无限次。听起来差别很小，但状态转移的方向完全相反，差之毫厘谬以千里。

我当年在一家金融科技公司面试，面试官出了零钱兑换，我洋洋洒洒写了一个01背包的解法，自我感觉良好。面试官说："你这个写的是什么背包？"我当时才意识到，完全背包和01背包在内层循环的方向上是相反的。

这个坑我掉进去过，所以今天要把这两者的区别讲得清清楚楚。不是死记硬背"完全背包内层正序，01背包内层倒序"，而是从原理上推导出为什么必须这样。

一、题目解析

题号：LeetCode 322. Coin Change

题目描述：给你一个整数数组 coins，代表不同面额的硬币；以及一个整数 amount，代表总金额。计算凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

示例：

  • 输入：coins = [1,2,5]，amount = 11，输出：3（5+5+1）
  • 输入：coins = [2]，amount = 3，输出：-1（无法凑成）
  • 输入：coins = [1]，amount = 0，输出：0

数据范围：1 ≤ coins.length ≤ 12，1 ≤ coins[i] ≤ 2^31-1，0 ≤ amount ≤ 10^4

核心考点：完全背包模型，状态转移，边界初始化，正序遍历的原理

二、DP思路推导

2.1 为什么是完全背包

先明确问题本质：每种面额的硬币可以用无限次，这就是完全背包的定义。

对比01背包：每件物品只能选或不选，最多一次。

完全背包：每件物品可以选0次、1次、2次……无限次。

2.2 状态定义

定义 dp[j] = 凑成金额 j 所需的最少硬币数

为什么用金额作为下标，而不是用硬币种数作为下标？因为我们要枚举的是"能凑成的金额"，每个金额对应一个最优解。硬币种数用外层循环遍历，金额用内层循环遍历。

2.3 二维DP的推导（理解本质）

先从二维DP推导，再压缩到一维。

定义 dp[i][j] = 使用前 i 种硬币，凑成金额 j 所需的最少硬币数

对于第 i 种硬币（面额 coins[i-1]），对于每个金额 j，有两种选择：

  1. 不使用第 i 种硬币：dp[i][j] = dp[i-1][j]

  2. 使用至少一枚第 i 种硬币：dp[i][j] = dp[i][j - coins[i-1]] + 1

注意：使用"至少一枚"的时候，状态转移是 dp[i][j-coins[i-1]] + 1，而不是 dp[i-1][j-coins[i-1]] + 1。

这是完全背包与01背包的核心区别！

  • 01背包：dp[i][j] = dp[i-1][j-weight] + value（用第i-1行，因为第i件只能用一次）
  • 完全背包：dp[i][j] = dp[i][j-weight] + value（用第i行，因为第i件可以无限使用）

为什么完全背包可以用第 i 行？因为 dp[i][j-coins[i-1]] 表示"用前i种硬币凑成 j-coins[i-1] 的最少数量"，在这个基础上再加一枚第i种硬币，就凑成了 j，而第 i 种硬币在这个子问题里已经可能被用过了，这正好满足"无限使用"的要求。

所以完全背包的二维转移方程：

dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i-1]] + 1)  当 j >= coins[i-1]
dp[i][j] = dp[i-1][j]                                   当 j < coins[i-1]

2.4 压缩到一维：正序的原因

把二维压缩到一维，关键是搞清楚：做空间压缩时，dp[j] 在被更新之前，代表的是什么？

一维数组 dp[j] 滚动更新，外层遍历硬币种类，内层遍历金额。

当内层从小到大遍历（正序）时：

  • 计算 dp[j] 时，dp[j - coins[i-1]] 已经被这一轮（第i种硬币）更新过
  • 这意味着 dp[j - coins[i-1]] 可能已经用了第 i 种硬币
  • 等价于二维DP中的 dp[i][j - coins[i-1]]——允许重复使用第 i 种硬币

完全背包内层正序 的原因就是这个：利用本轮已更新的值，允许同一种硬币使用多次。

如果内层从大到小遍历（倒序），计算 dp[j] 时 dp[j - coins[i-1]] 还没被本轮更新，等价于 dp[i-1][j-coins[i-1]]，就变成了01背包。

这才是"完全背包正序，01背包倒序"背后的本质原因，绝对不是死记硬背。

状态转移示意（coins=[1,2,5], amount=11）：

外层遍历硬币，内层正序遍历金额：

初始：dp = [0, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF]
            j=0   1    2    3    4    5    6    7    8    9   10   11

硬币=1：
  j=1: dp[1] = min(INF, dp[0]+1) = 1
  j=2: dp[2] = min(INF, dp[1]+1) = 2
  ...
  j=11: dp[11] = 11

硬币=2：
  j=2: dp[2] = min(2, dp[0]+1) = 1
  j=3: dp[3] = min(3, dp[1]+1) = 2
  j=4: dp[4] = min(4, dp[2]+1) = 2
  ...

硬币=5：
  j=5: dp[5] = min(3, dp[0]+1) = 1
  j=10: dp[10] = min(4, dp[5]+1) = 2
  j=11: dp[11] = min(7, dp[6]+1) = min(7, 3) = 3

2.5 边界条件

  • dp[0] = 0：凑成金额0需要0枚硬币
  • dp[j] = Integer.MAX_VALUE（j > 0）：初始化为无穷大，表示还无法凑成

注意：初始化为 Integer.MAX_VALUE 时，做 dp[j-coin] + 1 之前必须先判断 dp[j-coin] != Integer.MAX_VALUE，否则 +1 会溢出。

三、解法一：二维DP（推导清晰版）

public class CoinChange {
    
    /**
     * 322. 零钱兑换 - 二维DP（完全背包原始形式）
     * 时间复杂度：O(n * amount)，n为硬币种数
     * 空间复杂度：O(n * amount)
     */
    public int coinChange2D(int[] coins, int amount) {
        int n = coins.length;
        // dp[i][j] = 使用前i种硬币凑成金额j的最少硬币数
        int[][] dp = new int[n + 1][amount + 1];
        
        // 初始化：金额为0，0枚硬币；其余为MAX
        for (int j = 1; j <= amount; j++) {
            dp[0][j] = Integer.MAX_VALUE;  // 0种硬币无法凑成任何正数金额
        }
        
        for (int i = 1; i <= n; i++) {
            int coin = coins[i - 1];
            for (int j = 0; j <= amount; j++) {
                if (j < coin) {
                    // 当前硬币面额超过目标，无法使用
                    dp[i][j] = dp[i - 1][j];
                } else if (dp[i][j - coin] == Integer.MAX_VALUE) {
                    // 凑成j-coin还无法完成，只能选择不用第i种硬币
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 关键：用dp[i][j-coin]而非dp[i-1][j-coin]，允许重复用第i种
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coin] + 1);
                }
            }
        }
        
        return dp[n][amount] == Integer.MAX_VALUE ? -1 : dp[n][amount];
    }
}

四、解法二：一维DP（空间压缩，完全背包标准写法）

/**
 * 322. 零钱兑换 - 一维DP（完全背包空间优化）
 * 时间复杂度：O(n * amount)
 * 空间复杂度：O(amount)
 */
public int coinChange(int[] coins, int amount) {
    // dp[j] = 凑成金额j的最少硬币数
    int[] dp = new int[amount + 1];
    
    // 初始化：dp[0]=0，其余为MAX
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    
    // 外层遍历硬币（完全背包：硬币在外，金额在内）
    for (int coin : coins) {
        // 内层正序遍历金额（完全背包正序，允许重复使用）
        for (int j = coin; j <= amount; j++) {
            // 只有dp[j-coin]可达时才更新
            if (dp[j - coin] != Integer.MAX_VALUE) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
    }
    
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

状态转移Mermaid图：

五、解法三：记忆化搜索（DFS + memo）

很多人不知道，完全背包也可以用递归+记忆化来解，和DP完全等价，有时候思路更直观。

/**
 * 322. 零钱兑换 - 记忆化搜索
 * 时间复杂度：O(n * amount)
 * 空间复杂度：O(amount)
 */
public int coinChangeMemo(int[] coins, int amount) {
    int[] memo = new int[amount + 1];
    Arrays.fill(memo, -2);  // -2表示未计算，-1表示不可达
    return dfs(coins, amount, memo);
}

private int dfs(int[] coins, int remain, int[] memo) {
    if (remain == 0) return 0;
    if (remain < 0) return -1;
    if (memo[remain] != -2) return memo[remain];
    
    int minCount = Integer.MAX_VALUE;
    for (int coin : coins) {
        int sub = dfs(coins, remain - coin, memo);
        if (sub >= 0) {
            minCount = Math.min(minCount, sub + 1);
        }
    }
    
    memo[remain] = (minCount == Integer.MAX_VALUE) ? -1 : minCount;
    return memo[remain];
}

记忆化搜索和DP的关系：两者本质上等价，记忆化搜索是"自顶向下"（从目标金额出发，递归减小），DP是"自底向上"（从0出发，递推到目标）。理解了这个等价关系，遇到复杂DP两种方向都能尝试，哪个好写用哪个。

六、举一反三

同类完全背包题：

  1. LeetCode 518. 零钱兑换II：同样的输入，但求的是方案总数而非最少硬币数，转移方程改为求和（下篇详讲）
  2. LeetCode 279. 完全平方数：硬币变成了完全平方数，换汤不换药
  3. LeetCode 139. 单词拆分：字符串版的完全背包，物品是单词，背包容量是字符串长度

完全背包通用模板：

// 完全背包：最少次数
int[] dp = new int[capacity + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int item : items) {          // 外层遍历物品
    for (int j = item; j <= capacity; j++) {  // 内层正序遍历容量
        if (dp[j - item] != Integer.MAX_VALUE) {
            dp[j] = Math.min(dp[j], dp[j - item] + 1);
        }
    }
}

01背包通用模板（对比）：

// 01背包：内层倒序遍历容量
for (int item : items) {
    for (int j = capacity; j >= item; j--) {  // 内层倒序！
        dp[j] = Math.min(dp[j], dp[j - item] + cost);
    }
}

七、踩坑实录

坑一：完全背包写成了01背包

内层循环正序变倒序，结果变成了每种硬币只能用一次。这是我在面试中亲身踩过的坑。记住原理：正序允许重复使用（因为本轮更新的值还会被后续使用），倒序不允许重复使用。

坑二：Integer.MAX_VALUE + 1 溢出

dp 初始化为 Integer.MAX_VALUE，在做 dp[j-coin] + 1 时，如果 dp[j-coin] 还是 MAX_VALUE，+1 就会溢出变成负数，然后 min 操作就出问题了。必须先判断 dp[j-coin] != Integer.MAX_VALUE。

坑三：外层和内层循环能否互换

有人问：外层遍历金额，内层遍历硬币，能行吗？答案是：也能得到正确结果，但这是"组合"语义（区分顺序的排列）。在零钱兑换问题里，[1,2]和[2,1]是同一种方案，但如果换成"排列数"（如爬楼梯变体），就需要外层遍历金额内层遍历物品。具体在518里详细展开。

坑四：初始值设成-1导致混淆

有人把"不可达"初始化为-1，同时最终返回也是-1，导致代码逻辑混乱。我建议内部使用 Integer.MAX_VALUE 表示不可达，最后统一转换为-1返回，这样逻辑更清晰。

八、总结

零钱兑换是完全背包的标准题。核心在于理解完全背包为什么内层循环要正序：

正序遍历 = 允许同一物品反复使用 = 完全背包

倒序遍历 = 每个物品最多用一次 = 01背包

这个区别不是死记硬背，而是从二维DP压缩到一维时，对"是否已更新"的逻辑推导。搞清楚这一点，背包问题的核心就打通了一大半。

解法时间复杂度空间复杂度
二维DPO(n×amount)O(n×amount)
一维DP（空间压缩）O(n×amount)O(amount)
记忆化搜索O(n×amount)O(amount)
编辑此页
最近更新:
贡献者: xiaozhangge