尧图网站建设 
《Hello 算法》完全背包与零钱兑换问题状态设计、递推方程与“正序”空间优化的完整解析【免费下载链接】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本篇技术指南围绕仓库英文版教程 完全背包问题章节 展开系统讲解三个环环相扣的动态规划DP问题完全背包每件物品可取无限次、零钱兑换凑足金额所需最少硬币数与零钱兑换 II凑足金额的组合数。读完后你不仅能从零推导出它们各自的状态定义与状态转移方程还能理解为何这三类问题在做一维数组空间优化时必须采用正序遍历与 0-1 背包恰好相反并直接运行仓库中 10 余种语言的实现加以验证。一、问题全景三道题的差异只在“优化目标”与“计数方式”完全背包问题!!! question 给定 $n$ 个物品第 $i$ 个物品的重量为 $wgt[i-1]$、价值为 $val[i-1]$背包容量为 $cap$。每个物品可以被重复选取在不超过背包容量的前提下能装入背包的最大价值是多少它与此前讲解的 0-1 背包问题 只有一处不同0-1 背包中每种物品只有一件选中物品 $i$ 后只能回到前 $i-1$ 个物品继续决策而完全背包中每种物品数量不限放入物品 $i$ 之后仍可以在前 $i$ 个物品中继续选择。这意味着同一种物品可以多次入包也正是这一差别引出了完全不同的遍历方向。两道“零钱兑换”变体背包问题代表了一大类可互相转化的 DP 问题。把“物品”换成“硬币”、把“物品重量”换成“硬币面额”、把“背包容量”换成“目标金额 $amt$”就可以得到两类经典变体零钱兑换求最少硬币数$n$ 种硬币、面额为 $coins[i-1]$、每种可取多次凑出目标金额 $amt$ 所需的最少硬币数若无法凑出则返回 $-1$。零钱兑换 II求组合数同样的前提但改问“能凑出目标金额的硬币组合数量是多少”。两道变体的输入输出方向互为镜像完全背包目标是最大化价值、允许“不超过容量”零钱兑换则要求“恰好凑足金额”并最小化硬币数量零钱兑换 II 再退一步只统计方案数。理解了这一脉络三种解法的递推结构就可以逐一击破。二、完全背包的 DP 推导与实现状态定义与转移方程沿用 0-1 背包的记号定义状态 $dp[i, c]$ 为在前 $i$ 个物品中做选择、且背包容量为 $c$ 时能获得的最大价值。$dp$ 表为 $(n1) \times (cap1)$ 的矩阵其中 $i0$ 行与 $c0$ 列均表示“无可选物品 / 无容量”的退化情况。对每个状态 $[i, c]$ 只存在两种决策不放物品 $i$与 0-1 背包一致转移到 $[i-1, c]$放入物品 $i$与 0-1 背包不同由于仍可再次选择该物品转移到的是 $[i, c - wgt[i-1]]$而不是 $[i-1, \dots]$。于是状态转移方程为$$ dp[i, c] \max(dp[i-1, c], ; dp[i, c - wgt[i-1]] val[i-1]) $$与 0-1 背包的方程对比唯一的差异就是等号右侧第二项的“行号”从 $i-1$ 变成了 $i$。基础实现二维 $dp$ 表仓库英文版 Python 实现位于 en/codes/python/chapter_dynamic_programming/unbounded_knapsack.py核心逻辑如下中文版见 codes/python/chapter_dynamic_programming/unbounded_knapsack.pydef unbounded_knapsack_dp(wgt: list[int], val: list[int], cap: int) - int: Unbounded knapsack: Dynamic programming n len(wgt) # Initialize dp table dp [[0] * (cap 1) for _ in range(n 1)] # State transition for i in range(1, n 1): for c in range(1, cap 1): if wgt[i - 1] c: # If exceeds knapsack capacity, dont select item i dp[i][c] dp[i - 1][c] else: # The larger value between not selecting and selecting item i dp[i][c] max(dp[i - 1][c], dp[i][c - wgt[i - 1]] val[i - 1]) return dp[n][cap]代码中一个容易被忽略的关键点当选中物品 $i$ 时取的是当前行$dp[i][c - wgt[i-1]]$ 而不是上一行这保证了物品 $i$ 可以被连续多次纳入最优解。从双重循环结构可以看出该实现的时间复杂度为 $O(n \cdot cap)$、空间复杂度为 $O(n \cdot cap)$。空间优化为什么要“正序遍历”基础实现把 $dp$ 压缩成一维数组后唯一的难点是遍历顺序。从代码结构看当前状态 $dp[i][c]$ 同时依赖“上方的 $dp[i-1][c]$”和“左方同行的$dp[i][c - wgt[i-1]]$”。一维化后上方的旧值在覆盖前仍可用但“左方同行新值”只有在c 从小到大正序遍历时$dp[c - wgt[i-1]]$ 才恰好是本轮已经更新过的结果——这正是“允许重复取用当前物品”所要求的语义。反过来0-1 背包因为依赖“上一行的左方值”必须倒序遍历否则会错误地把“已放入一次的物品”再放一次。两题遍历方向相反的本质原因就在这里。def unbounded_knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) - int: Unbounded knapsack: Space-optimized dynamic programming n len(wgt) # Initialize dp table dp [0] * (cap 1) # State transition for i in range(1, n 1): # Traverse in forward order for c in range(1, cap 1): if wgt[i - 1] c: # If exceeds knapsack capacity, dont select item i dp[c] dp[c] else: # The larger value between not selecting and selecting item i dp[c] max(dp[c], dp[c - wgt[i - 1]] val[i - 1]) return dp[cap]原文档用 6 张分步图unbounded_knapsack_dp_comp_step1.png 至 step6完整演示了正序更新每一行的全过程建议对照 0-1 背包章节 中的“倒序”分步图对比学习——两套图的差异即是本小节结论的最好注解。空间优化后复杂度降为 $O(n \cdot cap)$ 时间、$O(cap)$ 空间。以仓库驱动代码中的测试数据wgt [1, 2, 3]、val [5, 11, 15]、cap 4运行最优方案为取两件重量为 2 的物品最大价值为 22两个函数输出一致可直接执行文件验证。三、零钱兑换最少硬币数最小化 “哨兵”初值与完全背包的对应关系零钱兑换可以被看成完全背包的特例二者存在如下对应与区别维度完全背包零钱兑换基本元素物品 → 重量 / 价值硬币 → 面额 / 计 1 枚容器背包容量 $cap$目标金额 $amt$优化目标最大化价值最小化硬币数约束语义“不超过”容量即可必须“恰好”凑足金额状态定义、转移方程与边界定义状态 $[i, a]$ 为子问题“用前 $i$ 种硬币凑出金额 $a$ 所需的最少硬币数”记作 $dp[i, a]$$dp$ 表规模为 $(n1) \times (amt1)$。相比完全背包转移方程有两处修改$\max$ 换成 $\min$选中硬币时价值项换为数量计数 1$$ dp[i, a] \min(dp[i-1, a], ; dp[i, a - coins[i-1]] 1) $$边界条件是本题最容易出错的地方目标金额为 0 时无需任何硬币故第一列全部为dp[i][0] 0没有硬币可用时任何金额 $0$ 都无法凑出属于“非法解”。为了让 $\min()$ 能自动过滤非法解第一行应初始化为 $\infty$。用amt 1代替正无穷规避整数溢出多数编程语言的整数类型没有“正无穷”只能退而使用int的最大值但这会让状态转移中的 1产生整数溢出。仓库源码给出的做法更巧妙因为凑出金额 $amt$ 最多也只需 $amt$ 枚硬币全部使用面额为 1 的极端情形所以用amt 1作为“不可能达到”的哨兵值安全且不会溢出。返回前检查 $dp[n, amt]$ 是否仍等于 $amt 1$若是则返回 $-1$。仓库英文版实现见 en/codes/python/chapter_dynamic_programming/coin_change.pydef coin_change_dp(coins: list[int], amt: int) - int: Coin change: Dynamic programming n len(coins) MAX amt 1 # Initialize dp table dp [[0] * (amt 1) for _ in range(n 1)] # State transition: first row and first column for a in range(1, amt 1): dp[0][a] MAX # State transition: rest of the rows and columns for i in range(1, n 1): for a in range(1, amt 1): if coins[i - 1] a: # If exceeds target amount, dont select coin i dp[i][a] dp[i - 1][a] else: # The smaller value between not selecting and selecting coin 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其空间优化版本coin_change_dp_comp与完全背包同理把数组压缩为dp [MAX] * (amt 1)并置dp[0] 0内层对金额正序遍历。原文档给出了 15 张分步图coin_change_dp_step1.png 至 step15展示哨兵初值如何被逐格“感染”为真实解可直观看到非法状态始终保持在 $amt1$。以仓库驱动数据coins [1, 2, 5]、amt 4运行两枚面额 2 的硬币即可凑足最少硬币数为2且无凑不出返回 -1的情况。时间与空间复杂度分别为 $O(n \cdot amt)$ 与 $O(amt)$优化后。四、零钱兑换 II统计组合数“相加”而非“比较”求和型转移方程本题只问“有多少种凑法”因此子问题退化为“用前 $i$ 种硬币凑出金额 $a$ 的组合数量”。组合的计数天然满足可加性——不选当前硬币的方案数与选当前硬币的方案数互斥且穷尽二者直接相加即可$$ dp[i, a] dp[i-1, a] dp[i, a - coins[i-1]] $$边界初始化也顺势改变金额为 0 时“什么都不选”本身就是一种空组合故第一列全部初始化为dp[i][0] 1没有硬币可用时凑不出任何正金额故第一行全部为 0。仓库英文版实现见 en/codes/python/chapter_dynamic_programming/coin_change_ii.pydef coin_change_ii_dp(coins: list[int], amt: int) - int: Coin change II: Dynamic programming n len(coins) # Initialize dp table dp [[0] * (amt 1) for _ in range(n 1)] # Initialize first column for i in range(n 1): dp[i][0] 1 # State transition for i in range(1, n 1): for a in range(1, amt 1): if coins[i - 1] a: # If exceeds target amount, dont select coin i dp[i][a] dp[i - 1][a] else: # Sum of the two options: not selecting and selecting coin i dp[i][a] dp[i - 1][a] dp[i][a - coins[i - 1]] return dp[n][amt]空间优化与“组合 vs 排列”的陷阱删除硬币维度后同样正序遍历dp[0] 1作为空组合的种子def coin_change_ii_dp_comp(coins: list[int], amt: int) - int: Coin change II: Space-optimized dynamic programming n len(coins) # Initialize dp table dp [0] * (amt 1) dp[0] 1 # State transition for i in range(1, n 1): # Traverse in forward order for a in range(1, amt 1): if coins[i - 1] a: # If exceeds target amount, dont select coin i dp[a] dp[a] else: # Sum of the two options: not selecting and selecting coin i dp[a] dp[a] dp[a - coins[i - 1]] return dp[amt]需要特别提醒硬币作为“物品种类”在外层循环、金额在内层循环这一层序保证了同一种硬币只被“组合式”地引入从而统计的是组合数而非排列数若把内外层互换同一组硬币的不同顺序会被重复计数。以仓库驱动数据coins [1, 2, 5]、amt 5运行可得到的 4 种组合为{1,1,1,1,1}、{1,1,1,2}、{1,2,2}与{5}输出组合数为4。复杂度同样为 $O(n \cdot amt)$ 时间、$O(amt)$ 优化空间。五、三题对照一张表记住全部套路问题目标操作符选中后的“项”首列初值首行初值返回异常完全背包价值最大$\max$$val[i-1]$00无零钱兑换硬币最少$\min$$1$0$amt1$哨兵仍为哨兵则 $-1$零钱兑换 II组合数量求和$dp[i, a-coins[i-1]]$10无三题的共同点$dp$ 表第 0 行 / 第 0 列承载边界语义不同问题需要“按需定制”初值所有状态转移只在本行左侧与上一行同列之间发生空间优化全部采用一维数组 正序遍历与 0-1 背包的倒序遍历形成鲜明对照其根本原因是“物品可取多次”时依赖同行左侧已更新值。仓库在codes/下按语言目录维护了同一组算法的等价实现英文版统一位于en/codes/例如 Java 版本见 unbounded_knapsack.java、coin_change.java 与 coin_change_ii.java。每个源文件都自带driver主函数与上文的示例数据可直接运行并逐行对照结果例如python3 en/codes/python/chapter_dynamic_programming/unbounded_knapsack.py python3 en/codes/python/chapter_dynamic_programming/coin_change.py python3 en/codes/python/chapter_dynamic_programming/coin_change_ii.py六、延伸阅读若希望进一步巩固这类“选或不选 / 选几次”的递推直觉建议沿着仓库文档继续阅读0-1 背包问题完全背包的对偶基础重点体会两者遍历方向的差异动态规划解题套路本节的“状态 → 转移方程 → 边界”三步法正是该套路的标准实践编辑距离问题 与 动态规划特性同一思想在“二维匹配”“最优子结构”上的更多变体。小结完全背包、零钱兑换与零钱兑换 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 《Hello 算法》完全背包与零钱兑换问题：状态设计、递推方程与“正序”空间优化的完整解析
《Hello 算法》完全背包与零钱兑换问题状态设计、递推方程与“正序”空间优化的完整解析【免费下载链接】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本篇技术指南围绕仓库英文版教程 完全背包问题章节 展开系统讲解三个环环相扣的动态规划DP问题完全背包每件物品可取无限次、零钱兑换凑足金额所需最少硬币数与零钱兑换 II凑足金额的组合数。读完后你不仅能从零推导出它们各自的状态定义与状态转移方程还能理解为何这三类问题在做一维数组空间优化时必须采用正序遍历与 0-1 背包恰好相反并直接运行仓库中 10 余种语言的实现加以验证。一、问题全景三道题的差异只在“优化目标”与“计数方式”完全背包问题!!! question 给定 $n$ 个物品第 $i$ 个物品的重量为 $wgt[i-1]$、价值为 $val[i-1]$背包容量为 $cap$。每个物品可以被重复选取在不超过背包容量的前提下能装入背包的最大价值是多少它与此前讲解的 0-1 背包问题 只有一处不同0-1 背包中每种物品只有一件选中物品 $i$ 后只能回到前 $i-1$ 个物品继续决策而完全背包中每种物品数量不限放入物品 $i$ 之后仍可以在前 $i$ 个物品中继续选择。这意味着同一种物品可以多次入包也正是这一差别引出了完全不同的遍历方向。两道“零钱兑换”变体背包问题代表了一大类可互相转化的 DP 问题。把“物品”换成“硬币”、把“物品重量”换成“硬币面额”、把“背包容量”换成“目标金额 $amt$”就可以得到两类经典变体零钱兑换求最少硬币数$n$ 种硬币、面额为 $coins[i-1]$、每种可取多次凑出目标金额 $amt$ 所需的最少硬币数若无法凑出则返回 $-1$。零钱兑换 II求组合数同样的前提但改问“能凑出目标金额的硬币组合数量是多少”。两道变体的输入输出方向互为镜像完全背包目标是最大化价值、允许“不超过容量”零钱兑换则要求“恰好凑足金额”并最小化硬币数量零钱兑换 II 再退一步只统计方案数。理解了这一脉络三种解法的递推结构就可以逐一击破。二、完全背包的 DP 推导与实现状态定义与转移方程沿用 0-1 背包的记号定义状态 $dp[i, c]$ 为在前 $i$ 个物品中做选择、且背包容量为 $c$ 时能获得的最大价值。$dp$ 表为 $(n1) \times (cap1)$ 的矩阵其中 $i0$ 行与 $c0$ 列均表示“无可选物品 / 无容量”的退化情况。对每个状态 $[i, c]$ 只存在两种决策不放物品 $i$与 0-1 背包一致转移到 $[i-1, c]$放入物品 $i$与 0-1 背包不同由于仍可再次选择该物品转移到的是 $[i, c - wgt[i-1]]$而不是 $[i-1, \dots]$。于是状态转移方程为$$ dp[i, c] \max(dp[i-1, c], ; dp[i, c - wgt[i-1]] val[i-1]) $$与 0-1 背包的方程对比唯一的差异就是等号右侧第二项的“行号”从 $i-1$ 变成了 $i$。基础实现二维 $dp$ 表仓库英文版 Python 实现位于 en/codes/python/chapter_dynamic_programming/unbounded_knapsack.py核心逻辑如下中文版见 codes/python/chapter_dynamic_programming/unbounded_knapsack.pydef unbounded_knapsack_dp(wgt: list[int], val: list[int], cap: int) - int: Unbounded knapsack: Dynamic programming n len(wgt) # Initialize dp table dp [[0] * (cap 1) for _ in range(n 1)] # State transition for i in range(1, n 1): for c in range(1, cap 1): if wgt[i - 1] c: # If exceeds knapsack capacity, dont select item i dp[i][c] dp[i - 1][c] else: # The larger value between not selecting and selecting item i dp[i][c] max(dp[i - 1][c], dp[i][c - wgt[i - 1]] val[i - 1]) return dp[n][cap]代码中一个容易被忽略的关键点当选中物品 $i$ 时取的是当前行$dp[i][c - wgt[i-1]]$ 而不是上一行这保证了物品 $i$ 可以被连续多次纳入最优解。从双重循环结构可以看出该实现的时间复杂度为 $O(n \cdot cap)$、空间复杂度为 $O(n \cdot cap)$。空间优化为什么要“正序遍历”基础实现把 $dp$ 压缩成一维数组后唯一的难点是遍历顺序。从代码结构看当前状态 $dp[i][c]$ 同时依赖“上方的 $dp[i-1][c]$”和“左方同行的$dp[i][c - wgt[i-1]]$”。一维化后上方的旧值在覆盖前仍可用但“左方同行新值”只有在c 从小到大正序遍历时$dp[c - wgt[i-1]]$ 才恰好是本轮已经更新过的结果——这正是“允许重复取用当前物品”所要求的语义。反过来0-1 背包因为依赖“上一行的左方值”必须倒序遍历否则会错误地把“已放入一次的物品”再放一次。两题遍历方向相反的本质原因就在这里。def unbounded_knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) - int: Unbounded knapsack: Space-optimized dynamic programming n len(wgt) # Initialize dp table dp [0] * (cap 1) # State transition for i in range(1, n 1): # Traverse in forward order for c in range(1, cap 1): if wgt[i - 1] c: # If exceeds knapsack capacity, dont select item i dp[c] dp[c] else: # The larger value between not selecting and selecting item i dp[c] max(dp[c], dp[c - wgt[i - 1]] val[i - 1]) return dp[cap]原文档用 6 张分步图unbounded_knapsack_dp_comp_step1.png 至 step6完整演示了正序更新每一行的全过程建议对照 0-1 背包章节 中的“倒序”分步图对比学习——两套图的差异即是本小节结论的最好注解。空间优化后复杂度降为 $O(n \cdot cap)$ 时间、$O(cap)$ 空间。以仓库驱动代码中的测试数据wgt [1, 2, 3]、val [5, 11, 15]、cap 4运行最优方案为取两件重量为 2 的物品最大价值为 22两个函数输出一致可直接执行文件验证。三、零钱兑换最少硬币数最小化 “哨兵”初值与完全背包的对应关系零钱兑换可以被看成完全背包的特例二者存在如下对应与区别维度完全背包零钱兑换基本元素物品 → 重量 / 价值硬币 → 面额 / 计 1 枚容器背包容量 $cap$目标金额 $amt$优化目标最大化价值最小化硬币数约束语义“不超过”容量即可必须“恰好”凑足金额状态定义、转移方程与边界定义状态 $[i, a]$ 为子问题“用前 $i$ 种硬币凑出金额 $a$ 所需的最少硬币数”记作 $dp[i, a]$$dp$ 表规模为 $(n1) \times (amt1)$。相比完全背包转移方程有两处修改$\max$ 换成 $\min$选中硬币时价值项换为数量计数 1$$ dp[i, a] \min(dp[i-1, a], ; dp[i, a - coins[i-1]] 1) $$边界条件是本题最容易出错的地方目标金额为 0 时无需任何硬币故第一列全部为dp[i][0] 0没有硬币可用时任何金额 $0$ 都无法凑出属于“非法解”。为了让 $\min()$ 能自动过滤非法解第一行应初始化为 $\infty$。用amt 1代替正无穷规避整数溢出多数编程语言的整数类型没有“正无穷”只能退而使用int的最大值但这会让状态转移中的 1产生整数溢出。仓库源码给出的做法更巧妙因为凑出金额 $amt$ 最多也只需 $amt$ 枚硬币全部使用面额为 1 的极端情形所以用amt 1作为“不可能达到”的哨兵值安全且不会溢出。返回前检查 $dp[n, amt]$ 是否仍等于 $amt 1$若是则返回 $-1$。仓库英文版实现见 en/codes/python/chapter_dynamic_programming/coin_change.pydef coin_change_dp(coins: list[int], amt: int) - int: Coin change: Dynamic programming n len(coins) MAX amt 1 # Initialize dp table dp [[0] * (amt 1) for _ in range(n 1)] # State transition: first row and first column for a in range(1, amt 1): dp[0][a] MAX # State transition: rest of the rows and columns for i in range(1, n 1): for a in range(1, amt 1): if coins[i - 1] a: # If exceeds target amount, dont select coin i dp[i][a] dp[i - 1][a] else: # The smaller value between not selecting and selecting coin 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其空间优化版本coin_change_dp_comp与完全背包同理把数组压缩为dp [MAX] * (amt 1)并置dp[0] 0内层对金额正序遍历。原文档给出了 15 张分步图coin_change_dp_step1.png 至 step15展示哨兵初值如何被逐格“感染”为真实解可直观看到非法状态始终保持在 $amt1$。以仓库驱动数据coins [1, 2, 5]、amt 4运行两枚面额 2 的硬币即可凑足最少硬币数为2且无凑不出返回 -1的情况。时间与空间复杂度分别为 $O(n \cdot amt)$ 与 $O(amt)$优化后。四、零钱兑换 II统计组合数“相加”而非“比较”求和型转移方程本题只问“有多少种凑法”因此子问题退化为“用前 $i$ 种硬币凑出金额 $a$ 的组合数量”。组合的计数天然满足可加性——不选当前硬币的方案数与选当前硬币的方案数互斥且穷尽二者直接相加即可$$ dp[i, a] dp[i-1, a] dp[i, a - coins[i-1]] $$边界初始化也顺势改变金额为 0 时“什么都不选”本身就是一种空组合故第一列全部初始化为dp[i][0] 1没有硬币可用时凑不出任何正金额故第一行全部为 0。仓库英文版实现见 en/codes/python/chapter_dynamic_programming/coin_change_ii.pydef coin_change_ii_dp(coins: list[int], amt: int) - int: Coin change II: Dynamic programming n len(coins) # Initialize dp table dp [[0] * (amt 1) for _ in range(n 1)] # Initialize first column for i in range(n 1): dp[i][0] 1 # State transition for i in range(1, n 1): for a in range(1, amt 1): if coins[i - 1] a: # If exceeds target amount, dont select coin i dp[i][a] dp[i - 1][a] else: # Sum of the two options: not selecting and selecting coin i dp[i][a] dp[i - 1][a] dp[i][a - coins[i - 1]] return dp[n][amt]空间优化与“组合 vs 排列”的陷阱删除硬币维度后同样正序遍历dp[0] 1作为空组合的种子def coin_change_ii_dp_comp(coins: list[int], amt: int) - int: Coin change II: Space-optimized dynamic programming n len(coins) # Initialize dp table dp [0] * (amt 1) dp[0] 1 # State transition for i in range(1, n 1): # Traverse in forward order for a in range(1, amt 1): if coins[i - 1] a: # If exceeds target amount, dont select coin i dp[a] dp[a] else: # Sum of the two options: not selecting and selecting coin i dp[a] dp[a] dp[a - coins[i - 1]] return dp[amt]需要特别提醒硬币作为“物品种类”在外层循环、金额在内层循环这一层序保证了同一种硬币只被“组合式”地引入从而统计的是组合数而非排列数若把内外层互换同一组硬币的不同顺序会被重复计数。以仓库驱动数据coins [1, 2, 5]、amt 5运行可得到的 4 种组合为{1,1,1,1,1}、{1,1,1,2}、{1,2,2}与{5}输出组合数为4。复杂度同样为 $O(n \cdot amt)$ 时间、$O(amt)$ 优化空间。五、三题对照一张表记住全部套路问题目标操作符选中后的“项”首列初值首行初值返回异常完全背包价值最大$\max$$val[i-1]$00无零钱兑换硬币最少$\min$$1$0$amt1$哨兵仍为哨兵则 $-1$零钱兑换 II组合数量求和$dp[i, a-coins[i-1]]$10无三题的共同点$dp$ 表第 0 行 / 第 0 列承载边界语义不同问题需要“按需定制”初值所有状态转移只在本行左侧与上一行同列之间发生空间优化全部采用一维数组 正序遍历与 0-1 背包的倒序遍历形成鲜明对照其根本原因是“物品可取多次”时依赖同行左侧已更新值。仓库在codes/下按语言目录维护了同一组算法的等价实现英文版统一位于en/codes/例如 Java 版本见 unbounded_knapsack.java、coin_change.java 与 coin_change_ii.java。每个源文件都自带driver主函数与上文的示例数据可直接运行并逐行对照结果例如python3 en/codes/python/chapter_dynamic_programming/unbounded_knapsack.py python3 en/codes/python/chapter_dynamic_programming/coin_change.py python3 en/codes/python/chapter_dynamic_programming/coin_change_ii.py六、延伸阅读若希望进一步巩固这类“选或不选 / 选几次”的递推直觉建议沿着仓库文档继续阅读0-1 背包问题完全背包的对偶基础重点体会两者遍历方向的差异动态规划解题套路本节的“状态 → 转移方程 → 边界”三步法正是该套路的标准实践编辑距离问题 与 动态规划特性同一思想在“二维匹配”“最优子结构”上的更多变体。小结完全背包、零钱兑换与零钱兑换 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考