完全背包问题详解 - 以零钱兑换 II 为例

1. 什么是完全背包问题

完全背包问题是动态规划中的经典问题，与01背包问题的区别在于：

01背包：每个物品只能使用一次
完全背包：每个物品可以使用无限次

2. 零钱兑换 II 问题分析

问题描述

给定不同面额的硬币和一个总金额，计算可以凑成总金额的硬币组合数。

为什么是完全背包？

物品：不同面额的硬币
背包容量：目标金额
特点：每种硬币可以使用无限次
目标：求组合数（而非最大价值）

3. 动态规划解法详解

3.1 状态定义

1

dp[j] = 凑成金额 j 的硬币组合数

3.2 初始化

1
2


dp[0] = 1  // 金额为0只有1种方案：不选任何硬币
dp[其他] = 0

3.3 状态转移方程

1

dp[j] += dp[j - coin]

含义：当前金额 j 的组合数 = 原有组合数 + 使用当前硬币后的组合数

3.4 遍历顺序（关键！）

1
2
3
4
5


for (int coin : coins) {          // 外层：遍历硬币
    for (int j = coin; j <= amount; j++) {  // 内层：遍历金额
        dp[j] += dp[j - coin];
    }
}

为什么这样遍历？

先遍历硬币，再遍历金额，保证了组合的唯一性
避免了重复计算（如 1+2 和 2+1 被当作不同组合）

4. 手工模拟过程

以 amount = 5, coins = [1, 2, 5] 为例：

初始状态

1

dp[0] = 1, dp[1] = 0, dp[2] = 0, dp[3] = 0, dp[4] = 0, dp[5] = 0

处理硬币 1

1
2
3
4
5
6


coin = 1
j = 1: dp[1] += dp[0] = 0 + 1 = 1
j = 2: dp[2] += dp[1] = 0 + 1 = 1  
j = 3: dp[3] += dp[2] = 0 + 1 = 1
j = 4: dp[4] += dp[3] = 0 + 1 = 1
j = 5: dp[5] += dp[4] = 0 + 1 = 1

结果：dp = [1, 1, 1, 1, 1, 1] 含义：只用硬币1，每个金额都有1种凑法

处理硬币 2

1
2
3
4
5


coin = 2
j = 2: dp[2] += dp[0] = 1 + 1 = 2  // 新增一种：用1个硬币2
j = 3: dp[3] += dp[1] = 1 + 1 = 2  // 新增一种：2+1
j = 4: dp[4] += dp[2] = 1 + 2 = 3  // 新增两种：2+2, 2+1+1
j = 5: dp[5] += dp[3] = 1 + 2 = 3  // 新增两种：2+2+1, 2+1+1+1

结果：dp = [1, 1, 2, 2, 3, 3]

处理硬币 5

1
2


coin = 5
j = 5: dp[5] += dp[0] = 3 + 1 = 4  // 新增一种：用1个硬币5

最终结果：dp = [1, 1, 2, 2, 3, 4]

验证组合

金额5的4种组合：

5 (1个硬币5)
2+2+1
2+1+1+1
1+1+1+1+1

5. 关键技术点

5.1 为什么内层循环正向遍历？

完全背包允许重复使用，所以从小到大更新
01背包需要逆向遍历，避免重复使用

5.2 组合 vs 排列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


// 组合（当前实现）：先遍历物品，再遍历背包
for (coin : coins) {
    for (j = coin; j <= amount; j++) {
        dp[j] += dp[j - coin];
    }
}

// 排列：先遍历背包，再遍历物品
for (j = 1; j <= amount; j++) {
    for (coin : coins) {
        if (j >= coin) {
            dp[j] += dp[j - coin];
        }
    }
}

5.3 空间优化

使用一维数组而非二维数组
空间复杂度从 O(n×amount) 优化到 O(amount)

6. 完全背包模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


// 模板：完全背包求组合数
vector<int> dp(target + 1, 0);
dp[0] = 1;

for (int item : items) {           // 遍历物品
    for (int j = item; j <= target; j++) {  // 遍历背包（正向）
        dp[j] += dp[j - item];     // 状态转移
    }
}
return dp[target];

7. 复杂度分析

时间复杂度：O(n × amount)，其中 n 是硬币种类数
空间复杂度：O(amount)

8. 相关变形题目

零钱兑换：求最少硬币数（最值问题）
组合总和IV：求排列数（改变遍历顺序）
分割等和子集：01背包变形
目标和：01背包变形

完全背包问题的核心在于理解状态转移和遍历顺序，掌握了这个模板，可以解决很多相关的动态规划问题。