完全背包与换零钱 DP
每件物品可以使用任意多次
完全背包与换零钱 DP 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
无限件物品
在完全背包中，每件物品都可以拿取任意多次。请把它想象成售货机中的硬币，而不是一堆数量固定的物品。
一个微小的变化
与 0/1 背包相比，唯一的变化是循环方向翻转。对于完全背包，要让容量从小到大正向遍历。
正向重复使用正是关键
正向遍历时，dp[w - coin] 可能已经包含了当前物品。正是这种有意的重复使用，让您能够再次拿取它。
认识零钱兑换
经典的零钱兑换问题要求用总和为指定金额的最少硬币数。它是使用最小值而不是最大值的完全背包 DP。
定义状态
令 dp[a] 表示凑出金额 a 所需的最少硬币数。先设置 dp[0] = 0，因为凑出 0 不需要硬币。
dp = [float("inf")] * (amount + 1)
dp[0] = 0用无穷大表示无法实现
无法达到的金额初始值设为无穷大。如果某个金额在最后仍为无穷大，就说明没有任何硬币组合可以凑出它。
状态转移
对于每种硬币，尝试更新它能够达到的每个金额。取剩余金额的最小值
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)为什么要正向遍历
让金额从小到大遍历，可以使 dp[a - coin] 已经计入当前硬币。这样同一枚硬币才能贡献多次。
改为统计方案数
将 min+1 换成求和，就可以统计凑出每个金额的方案数。把硬币循环放在外层，可以避免重复统计不同顺序。
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]读取结果
答案保存在 dp[amount] 中。在最小值版本中，无穷大的值表示目标金额无法凑出。
0/1 背包与完全背包
请记住这一个切换点：容量反向遍历表示每件物品只能使用一次，正向遍历表示可以无限使用。表格相同，遍历方向相反。
快速检查
测试是什么让背包变成完全背包。
回顾
您将循环改为正向遍历，以支持无限次使用，并用最小值构建最少硬币数的零钱兑换，用求和统计总方案数。💰
常见问题解答
「完全背包与换零钱 DP」课时是免费的吗？
是的 — 「完全背包与换零钱 DP」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「完全背包与换零钱 DP」这节课中我会学到什么？
每件物品可以使用任意多次 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「完全背包与换零钱 DP」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 0/1 背包：取或不取
- 空间优化的背包
- 完全背包与换零钱 DP
- 子集和与划分