Hello 算法：完全背包、零钱兑换与零钱兑换 II —— 动态规划中“正序遍历“的空间优化

Hello 算法完全背包、零钱兑换与零钱兑换 II —— 动态规划中正序遍历的空间优化【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本文基于《Hello 算法》动态规划章节的完全背包问题文档系统讲解完全背包问题的状态转移推导、代码实现与空间优化并深入剖析其两个经典变种——零钱兑换求最少硬币数与零钱兑换 II求硬币组合数。读完后你将能够独立推导物品可重复选取这一约束下的 DP 方程并理解为什么完全背包的空间优化必须使用正序遍历与 0-1 背包的倒序遍历正好相反同时掌握用amt 1代替∞避免整数溢出的工程技巧。一、完全背包问题1.1 问题定义给定 n 个物品第 i 个物品的重量为wgt[i-1]、价值为val[i-1]和一个容量为cap的背包。每个物品可以重复选取问在限定背包容量下能放入物品的最大价值。文档给出的示例数据也与源码 Driver Code 一致为wgt [1, 2, 3]val [5, 11, 15]cap 4。可以验证背包容量 4 时最优解是放入 4 份重量 1 的物品价值 20或者 2 份重量 2 的物品价值 22因此最终答案应为 22。1.2 与 0-1 背包的本质区别完全背包问题和 0-1 背包问题非常相似区别仅在于不限制物品的选择次数。这正是两题状态转移的源头差异在 0-1 背包中每种物品只有一个因此将物品 i 放入背包后只能从前 i-1 个物品中选择在完全背包中每种物品的数量是无限的因此将物品 i 放入背包后仍可以从前 i 个物品中选择包括物品 i 本身。状态[i, c]考虑前 i 个物品、容量为 c 时的最大价值的变化分为两种情况不放入物品 i与 0-1 背包相同转移至[i-1, c]放入物品 i与 0-1 背包不同转移至[i, c - wgt[i-1]]注意行号仍是 i 而不是 i-1。从而状态转移方程变为$$ dp[i, c] \max(dp[i-1, c],\ dp[i, c - wgt[i-1]] val[i-1]) $$1.3 代码实现只有一处从 i-1 变为 i在 Python 参考实现 unbounded_knapsack.py 中二维 DP 版本unbounded_knapsack_dp的核心循环如下def unbounded_knapsack_dp(wgt: list[int], val: list[int], cap: int) - int: 完全背包动态规划 n len(wgt) # 初始化 dp 表 dp [[0] * (cap 1) for _ in range(n 1)] # 状态转移 for i in range(1, n 1): for c in range(1, cap 1): if wgt[i - 1] c: # 若超过背包容量则不选物品 i dp[i][c] dp[i - 1][c] else: # 不选和选物品 i 这两种方案的较大值 dp[i][c] max(dp[i - 1][c], dp[i][c - wgt[i - 1]] val[i - 1]) return dp[n][cap]把这段代码与 0-1 背包的实现 knapsack.py 中的knapsack_dp逐行对比会发现两者唯一的区别就在转移式中选物品那一支的下标# 0-1 背包knapsack_dpdp[i - 1][c - wgt[i - 1]] val[i - 1] # 完全背包unbounded_knapsack_dpdp[i][c - wgt[i - 1]] val[i - 1]dp[i-1][...]意味着选完物品 i 后不能再选物品 idp[i][...]意味着选完物品 i 后还可以继续选物品 i——一个下标之差精确编码了物品是否可重复选取这一语义。C 实现 unbounded_knapsack.cpp 中的unboundedKnapsackDP逻辑完全一致。1.4 空间优化正序遍历是关键二维表dp[i][c]只依赖于上一行的dp[i-1][c]与同一行左侧的dp[i][c - wgt[i-1]]。删除第一维、用一维数组dp[c]滚动更新时遍历方向决定了dp[c - wgt[i-1]]取到的是上一轮的值还是本轮刚更新的值完全背包当前状态需要引用本轮已更新的同状态体现可重复选取因此对每一行必须正序遍历c从 1 到 cap0-1 背包当前状态必须引用上一轮未更新的值体现只选一次因此必须倒序遍历c从 cap 到 1。这个遍历顺序与 0-1 背包正好相反。文档配了 6 张连续动图展示一维化后的转移过程状态从左边和上边即左侧和上方扩散而来其中一张步骤图如下完整 6 步序列见 unbounded_knapsack_dp_comp_step1.png 至 unbounded_knapsack_dp_comp_step6.png。以示例数据手动推演一遍正序遍历可以更直观地看到同轮复用如何发生处理物品 3重 3、值 15这一轮c从 1 增至 4当c 4时dp[4] max(dp[4], dp[4-3] 15)而dp[1]在本轮c 1时已经因选取物品 3 更新为 15于是dp[4] max(22, 15 15) 22……最终dp[4] 22即 2 份物品 2价值 2×11。若换成倒序遍历dp[1]在c4时还未更新选两份物品 2的路径就不存在——这正是遍历顺序决定语义的根源。空间优化后的 Python 实现仅需将数组dp的第一维删除对应 unbounded_knapsack.py 的unbounded_knapsack_dp_compdef unbounded_knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) - int: 完全背包空间优化后的动态规划 n len(wgt) # 初始化 dp 表 dp [0] * (cap 1) # 状态转移 for i in range(1, n 1): # 正序遍历 for c in range(1, cap 1): if wgt[i - 1] c: # 若超过背包容量则不选物品 i dp[c] dp[c] else: # 不选和选物品 i 这两种方案的较大值 dp[c] max(dp[c], dp[c - wgt[i - 1]] val[i - 1]) return dp[cap]源码文件末尾的 Driver Code 同时运行两个版本输入wgt [1, 2, 3]、val [5, 11, 15]、cap 4两版本输出一致。C 版本 unbounded_knapsack.cpp 的unboundedKnapsackDPComp同样采用for (int c 1; c cap; c)的正序循环。小结完全背包空间优化的两条规则——① 删除物品维度dp[c]初值为 0价值类问题容量为 0 时价值自然为 0② 容量维度正序遍历。与 0-1 背包初值 0、倒序遍历形成对照这是面试与竞赛中最高频的易错点之一。二、零钱兑换问题完全背包的特例背包问题是一大类动态规划问题的代表其拥有很多变种例如零钱兑换问题。2.1 问题定义给定 n 种硬币第 i 种硬币的面值为coins[i - 1]目标金额为amt每种硬币可以重复选取问能够凑出目标金额的最少硬币数量。如果无法凑出目标金额则返回 -1。示例数据为coins [1, 2, 5]amt 4源码 Driver Code 使用完全相同的输入预期最少硬币数为 2即 2 2。2.2 与完全背包的联系与不同零钱兑换可以看作完全背包问题的一种特殊情况两者可以相互转换同时存在三点关键差异维度完全背包零钱兑换概念对应物品 / 重量 / 背包容量 / 价值硬币 / 面值 / 目标金额 / 硬币数量优化方向最大化价值max最小化硬币数min容量语义不超过容量 cap 的最大价值恰好凑到 amt 的最少硬币数恰好 vs 不超过的差异直接体现在边界初始化上完全背包首行首列全 0容量为 0 时价值 0且允许没装满零钱兑换首列全 0、首行除首列外为无效解。2.3 三步推导 DP第一步定义状态得到 dp 表。状态[i, a]对应的子问题为前 i 种硬币能够凑出金额 a 的最少硬币数量记为dp[i, a]。二维 dp 表的尺寸为(n1) × (amt1)。第二步最优子结构推导状态转移方程。与完全背包的方程相比只有两点差异本题要求最小值因此将运算符max()更改为min()优化主体是硬币数量而非商品价值因此在选中硬币时执行1即可。$$ dp[i, a] \min(dp[i-1, a],\ dp[i, a - coins[i-1]] 1) $$第三步确定边界条件和状态转移顺序。当目标金额为 0 时凑出它的最少硬币数量为 0即首列所有dp[i, 0]都等于 0二维表默认初值 0 恰好满足无需显式初始化当无硬币时无法凑出任意 0 的目标金额是无效解。为使min()函数能够识别并过滤无效解用∞表示它们即令首行所有dp[0, a]a 0都等于∞。2.4 代码实现用 amt 1 代替 ∞ 防溢出大多数编程语言并未提供∞变量只能使用整型int的最大值来代替。而这又会导致大数越界状态转移方程中的1操作可能发生溢出。为此源码采用数字amt 1来表示无效解——因为凑出amt的硬币数量最多为amt全用面值为 1 的硬币任何超过amt的值都必然无效且amt 1加 1 后最多为amt 2远不会触及整数上限。最后返回前判断dp[n, amt]是否等于amt 1若是则返回 -1。Python 参考实现 coin_change.py 完整呈现了这一技巧def coin_change_dp(coins: list[int], amt: int) - int: 零钱兑换动态规划 n len(coins) MAX amt 1 # 初始化 dp 表 dp [[0] * (amt 1) for _ in range(n 1)] # 状态转移首行首列 for a in range(1, amt 1): dp[0][a] MAX # 状态转移其余行和列 for i in range(1, n 1): for a in range(1, amt 1): if coins[i - 1] a: # 若超过目标金额则不选硬币 i dp[i][a] dp[i - 1][a] else: # 不选和选硬币 i 这两种方案的较小值 dp[i][a] min(dp[i - 1][a], dp[i][a - coins[i - 1]] 1) return dp[n][amt] if dp[n][amt] ! MAX else -1注意二维表初始化时首列dp[i][0]保持 0与 2.3 的边界条件一致而首行dp[0][a]被显式置为MAX amt 1。C 实现 coin_change.cpp 的coinChangeDP结构相同。文档用 15 张连续动图展示了零钱兑换的完整填表过程与完全背包非常相似注意恰好语义使首行的无效解amt1像波浪一样向右传播完整 15 步序列见 coin_change_dp_step1.png 至 coin_change_dp_step15.png。2.5 空间优化零钱兑换的空间优化处理方式与完全背包一致同样正序遍历。但初值有一个本质区别——因为要求恰好凑到容量金额为 0 以外的位置初始都是无效解所以一维表要整体初始化为MAX amt 1仅dp[0] 0def coin_change_dp_comp(coins: list[int], amt: int) - int: 零钱兑换空间优化后的动态规划 n len(coins) MAX amt 1 # 初始化 dp 表 dp [MAX] * (amt 1) dp[0] 0 # 状态转移 for i in range(1, n 1): # 正序遍历 for a in range(1, amt 1): if coins[i - 1] a: # 若超过目标金额则不选硬币 i dp[a] dp[a] else: # 不选和选硬币 i 这两种方案的较小值 dp[a] min(dp[a], dp[a - coins[i - 1]] 1) return dp[amt] if dp[amt] ! MAX else -1对比 0-1 背包空间优化dp [0] * (cap 1) 倒序遍历与完全背包空间优化dp [0] * (cap 1) 正序遍历零钱兑换空间优化为dp [MAX] * (amt1)、dp[0] 0 正序遍历——初值编码了恰好/不超过的语义遍历方向编码了可重复/不可重复的语义两者正交组合出所有变种的优化规则。三、零钱兑换问题 II求组合数量3.1 问题定义给定 n 种硬币第 i 种硬币的面值为coins[i - 1]目标金额为amt每种硬币可以重复选取问凑出目标金额的硬币组合数量注意求的是组合数而非最少数量且不计顺序。示例数据coins [1, 2, 5]amt 5预期答案为 4 种组合[5]、[1,1,1,2]、[1,1,3… ]——实际为[5]、[1,1,1,1,1]、[1,1,1,2]、[1,2,2]。3.2 状态转移从 min 到求和相比于上一题本题目标是求组合数量因此子问题变为前 i 种硬币能够凑出金额 a 的组合数量。而 dp 表仍然是尺寸为(n1) × (amt 1)的二维矩阵。当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量之和加法原理状态转移方程为$$ dp[i, a] dp[i-1, a] dp[i, a - coins[i-1]] $$边界条件与零钱兑换 I 不同当目标金额为 0 时无须选择任何硬币即可凑出目标金额空方案算一种因此应将首列所有dp[i, 0]都初始化为1而不是 0当无硬币时无法凑出任何 0 的目标金额因此首行所有dp[0, a]都等于 0二维表默认初值 0 恰好满足。3.3 代码实现Python 参考实现 coin_change_ii.pydef coin_change_ii_dp(coins: list[int], amt: int) - int: 零钱兑换 II动态规划 n len(coins) # 初始化 dp 表 dp [[0] * (amt 1) for _ in range(n 1)] # 初始化首列 for i in range(n 1): dp[i][0] 1 # 状态转移 for i in range(1, n 1): for a in range(1, amt 1): if coins[i - 1] a: # 若超过目标金额则不选硬币 i dp[i][a] dp[i - 1][a] else: # 不选和选硬币 i 这两种方案之和 dp[i][a] dp[i - 1][a] dp[i][a - coins[i - 1]] return dp[n][amt]3.4 空间优化删除硬币维度空间优化处理方式相同——同样删除硬币维度、同样正序遍历选当前硬币支引用同轮已更新的dp[a - coins[i-1]]保证组合按硬币种类有序枚举、不产生重复排列def coin_change_ii_dp_comp(coins: list[int], amt: int) - int: 零钱兑换 II空间优化后的动态规划 n len(coins) # 初始化 dp 表 dp [0] * (amt 1) dp[0] 1 # 状态转移 for i in range(1, n 1): # 正序遍历 for a in range(1, amt 1): if coins[i - 1] a: # 若超过目标金额则不选硬币 i dp[a] dp[a] else: # 不选和选硬币 i 这两种方案之和 dp[a] dp[a] dp[a - coins[i - 1]] return dp[amt]C 实现可见 coin_change_ii.cpp各语言实现Java、Go、Rust 等均遵循同一套转移式与遍历方向。四、横向对照三个问题的 DP 要素速查要素0-1 背包完全背包零钱兑换 I零钱兑换 II物品约束每种选 0/1 次可重复选取可重复选取可重复选取优化目标最大价值最大价值最少硬币数组合数量转移式max(dp[i-1][c], dp[i-1][c-w]v)max(dp[i-1][c], dp[i][c-w]v)min(dp[i-1][a], dp[i][a-coins]1)dp[i-1][a] dp[i][a-coins]容量语义不超过不超过恰好恰好二维表初值全 0全 0首列 0首行amt1首列 1其余 0一维表初值[0]*(cap1)[0]*(cap1)[MAX]*(amt1),dp[0]0[0]*(amt1),dp[0]1遍历方向一维倒序正序正序正序特殊返回值无无无效解返回 -1无参考实现knapsack.pyunbounded_knapsack.pycoin_change.pycoin_change_ii.py三个要点可以一句话记忆转移式中选物品那支的行号i 还是 i-1决定物品能否重复一维化后的遍历方向必须与之保持一致i-1 对应倒序、i 对应正序恰好语义靠非零初值无效解标记表达不超过语义靠全零初值表达。五、复杂度与适用前提以二维 DP 表述四个问题的时间复杂度均为O(n × cap)零钱兑换系列为O(n × amt)空间复杂度O(n × cap)空间优化后降为O(cap)。从源码结构看所有参考实现都未对物品重量/硬币面值为 0等非法输入做额外校验使用时需保证wgt[i] ≥ 1、coins[i] ≥ 1零钱兑换 I 的amt 1无效解技巧依赖硬币数最多为 amt的上界要求存在面值为 1 的硬币时才总能凑出否则最终返回 -1行为正确。以上实现均在仓库各语言目录中提供了等价版本如 codes/cpp/chapter_dynamic_programming/可对照阅读以验证不同语言下同一套 DP 模板的写法一致性。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考