完全背包与零钱兑换 II
通过正向遍历容量允许重复使用物品，并使用这一变体解决零钱兑换 II（统计方案数）和切割钢条问题。
完全背包与零钱兑换 II 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
完全背包概念
在完全背包中，每个物品可以选择任意多次（不同于每个物品最多使用一次的 0/1 背包）。状态定义相同——dp[c] = 容量为 c 时可以达到的最大价值——但遍历方向发生了变化。由于物品可以重复使用，更新 dp[c] 时需要允许再次使用当前物品，因此要从左到右（正向）遍历容量。
正向遍历实现重复使用
回顾一下，在 0/1 背包中，我们从右到左遍历以防止重复使用。在完全背包中则相反：要从左到右遍历。计算 dp[c] 时，dp[c-w] 已经在当前遍历中更新过，这意味着物品 i 可能已经被包含。正是我们想要的效果：物品 i 可以再次添加到一个已经包含物品 i 的解中。
def unbounded_knapsack(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(w, W + 1): # iterate LEFT TO RIGHT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print(unbounded_knapsack(weights, values, 7)) # 9硬币兑换 II：计算方案数
硬币兑换 II要求：给定硬币面额和一个金额，计算凑出该金额的不同方案数（每种硬币都可以无限次使用）。这是完全背包的一种变体，不再是最大化价值，而是计算 combinations。将 dp[c] 定义为凑出金额 c 的方案数。基本情况：dp[0] = 1（凑出 0 的方法只有一种：什么都不取）。
硬币兑换 II 实现
对于每种硬币，从左到右遍历金额并累加：dp[c] += dp[c - coin]。基本情况 dp[0] = 1 为计数提供初始值。请注意，外层循环遍历硬币，内层循环遍历金额——这样自然得到combinations 计数（而不是 permutations），因为每种硬币面额都只作为外层遍历的一次处理对象。
def change(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make amount 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
print(change(5, [1, 2, 5])) # 4
print(change(3, [2])) # 0
print(change(10, [10])) # 1combinations 与 permutations 的区别
循环的顺序至关重要。如果将金额放在外层循环、硬币放在内层循环，计算的就是permutations（顺序有影响）。对于 amount=5、硬币为 [1,2] 的情况，1+2+2 和 2+1+2 会被分别计数。如果将硬币放在外层循环，计算的就是combinations（顺序没有影响）：1+2+2 和 2+1+2 被视为同一种方案。硬币兑换 II 要求计算 combinations，因此硬币应作为外层循环。
# Count COMBINATIONS (order does not matter) — coin outer loop
def combinations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins: # coin outer
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
# Count PERMUTATIONS (order matters) — amount outer loop
def permutations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for c in range(1, amount + 1): # amount outer
for coin in coins:
if c >= coin:
dp[c] += dp[c - coin]
return dp[amount]
print(combinations(5, [1,2,5])) # 4
print(permutations(5, [1,2,5])) # 13钢条切割问题
这是另一个经典的完全背包问题：给定长度为 n 的钢条，以及长度从 1 到 n 的每种钢条价格，找出最优切割方案，使收益最大。每段长度为 l 的钢条可以按 price[l] 出售，并且各段可以重复使用（钢条可以切成多段相同长度的部分）。这可以直接映射为完全背包，其中 W = n，物品就是不同的切割长度。
def rod_cutting(prices, n):
# prices[i] = price of rod of length i+1
dp = [0] * (n + 1)
for length in range(1, n + 1): # each cut length
price = prices[length - 1]
for c in range(length, n + 1):
dp[c] = max(dp[c], dp[c - length] + price)
return dp[n]
prices = [1, 5, 8, 9, 10, 17, 17, 20]
print(rod_cutting(prices, 8)) # 22硬币兑换 I：最少硬币数
硬币兑换 I（一个不同的问题）要求使用最少数量的硬币凑出目标金额。这里 dp[c] = 凑出金额 c 所需的最少硬币数。递推式为：dp[c] = min(dp[c], dp[c - coin] + 1)。除 dp[0] = 0 外，将所有条目初始化为 inf。这同样是完全背包问题（硬币可以重复使用），因此要从左到右遍历。若 dp[amount] 有限，则返回它；否则返回 -1。
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] = min(dp[c], dp[c - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coinChange([1,5,6,9], 11)) # 2 (5+6 or other combos)
print(coinChange([2], 3)) # -1关键区别：最大值、最小值与计数
完全背包的三种变体对 dp[c-coin] 使用不同的操作：最大化价值：dp[c] = max(dp[c], dp[c-w] + v)；初始化为 0。最小化成本：dp[c] = min(dp[c], dp[c-coin] + 1)；初始化为 inf，dp[0]=0。计算方案数：dp[c] += dp[c-coin]；初始化为 0，dp[0]=1。在面试题中识别出适用的变体，就等于成功了一半。
复杂度与面试技巧
所有完全背包变体的时间复杂度都是 O(n × W)，空间复杂度都是 O(W)，其中 n 是物品类型的数量，W 是目标金额。对于硬币问题，n 是硬币面额的数量。面试时，请说明变体类型（最大值、最小值或计数），写出一维 DP，并明确外层循环遍历的是硬币还是金额——出题者知道，这一区别能够检验您对 DP 的深入理解。
辨别完全背包与 0/1 背包
可以根据以下信号判断适用的变体：可以无限次重复使用 → 完全背包（正向遍历）；每个物品恰好使用一次 → 0/1 背包（逆向遍历）；题目说明“可以使用任意次数”“供应无限”或“允许重复使用” → 完全背包。示例：硬币兑换、钢条切割、整数拆分都属于完全背包。子集和、分割、0/1 背包属于 0/1 背包。判断错误会导致难以调试的错误答案。
整数拆分与其他变体
整数拆分（LeetCode 343）：将整数 n 拆分为至少 2 个正整数，使它们的乘积最大化。这是一个完全背包问题，其中“物品”是从 2 到 n-1 的整数。将 dp[i] 定义为总和为 i 的整数的最大乘积。对于从 2 到 i 的每个物品 j，dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))。这说明完全背包模式可以推广到硬币场景之外。
def integerBreak(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i):
dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))
return dp[n]
print(integerBreak(10)) # 36 (3+3+4 = 3*3*4 = 36)快速检查
测试您对本课数据结构 & 算法——编程面试准备相关概念的理解。
课程回顾
本课您学习了：完全背包从左到右遍历容量，以允许重复使用物品，硬币兑换 II 通过将硬币放在外层循环来计算 combinations，以及三种变体——最大化、最小化和计数——的区别仅在于 DP 操作和初始化方式不同。接下来我们将使用 0/1 背包解决分割等和子集问题。
常见问题解答
「完全背包与零钱兑换 II」课时是免费的吗？
是的 — 「完全背包与零钱兑换 II」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「完全背包与零钱兑换 II」这节课中我会学到什么？
通过正向遍历容量允许重复使用物品，并使用这一变体解决零钱兑换 II（统计方案数）和切割钢条问题。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「完全背包与零钱兑换 II」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 0/1 背包与空间优化
- 完全背包与零钱兑换 II
- 等和子集分割
- 带正负号的目标和