教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载导读背包问题Knapsack Problem是动态规划中最经典、最核心的模型之一也是面试与竞赛中出现频率极高的考点。本指南以 LogicStack-LeetCode 仓库的 Index/背包 DP.md 索引为核心骨架结合仓库内 279、322、416、494、518、879 等题目的完整题解源码系统讲解「01 背包」「完全背包」「多维背包」「分组背包」等子模型的判别方法、状态定义、状态转移方程、滚动数组与一维空间优化技巧。读完本文你将掌握一套「识别背包模型 → 设计状态 → 推导转移 → 优化空间」的通用解题流水线并能直接对照仓库中每道题的 Java 实现进行验证与练习。一、背包问题一套可以复用的动态规划框架1.1 什么是背包问题背包问题的本质是一个组合优化问题给定若干「物品」每个物品有体积成本和价值收益要求在不超出背包容量的前提下通过选择物品达到「全局最优」最大价值 / 最小成本或「特定状态」恰好凑出某个值 / 凑出某个值的方案数。仓库题解中反复强调的一个判别习惯是见 322. 零钱兑换中等.md当看到题目是给定一些「物品」让我们从中进行选择以达到「最大价值」或者「特定价值」时我们应该联想到「背包问题」。被选物品之间不需要满足特定关系只需要选择物品以达到「全局最优」或者「特定状态」即可。1.2 如何根据「选择次数限制」判别背包子模型拿到一道题先回答三个问题判别维度01 背包完全背包多维背包分组背包每种物品可选次数至多 1 次无限次至多 1 次每组至多选 1 个容量维度个数1 个1 个2 个及以上1 个典型题416、494322、518、2794740 和 1 两个维度1155骰子分组仓库中 416. 分割等和子集中等(上).md.md) 将背包模型做了系统总结而 322、518、279 三题则分别演示了完全背包在「求最少物品数」「求方案数」「求最少物品数」三个场景下的变形。下文将以这些仓库源码为实例逐步展开。二、题目索引仓库「背包 DP」专题完整清单以下是 LogicStack-LeetCode 仓库 Index/背包 DP.md 收录的全部背包类题目难度与推荐指数沿用索引原文题解列已转换为仓库内相对路径便于直接查阅题目仓库题解难度推荐指数279. 完全平方数题解中等322. 零钱兑换题解中等416. 分割等和子集上题解上.md)中等416. 分割等和子集下题解下.md)中等474. 一和零题解中等494. 目标和题解中等518. 零钱兑换 II题解中等638. 大礼包仓库 LeetCode/631-640/ 目录下中等879. 盈利计划题解困难1049. 最后一块石头的重量 II题解中等1155. 掷骰子的N种方法题解中等1449. 数位成本和为目标值的最大数字题解困难1995. 统计特殊四元组题解简单从「简单 → 中等 → 困难」的难度梯度可以看出背包模型可以覆盖从入门到进阶的完整链路而 416 上下两篇则专门用于精讲 01 背包从「间接求解」到「直接求解」的思维转换是仓库中背包系列的核心篇章。三、完全背包实战322. 零钱兑换3.1 题目与背包模型判别给定不同面额的硬币coins和一个总金额amount编写一个函数计算凑成总金额所需的最少硬币个数若无任何硬币组合能组成总金额返回-1。每种硬币数量无限。约束1 coins.length 121 coins[i] 2^31 - 10 amount 10^4。硬币相当于物品每种硬币可选择无限次因此属于完全背包目标是最小化「使用的硬币个数」。3.2 状态定义与初始化完全背包的原始状态定义是两维的第一维i代表物品编号前 i 件物品第二维j代表容量背包容量 / 目标总和。定义f[i][j]为考虑前 i 件物品、凑成总和为 j 所需要的最少硬币数量。初始化时引入「哨兵」思想令f[0][x]代表「不考虑任何物品」的情况于是f[0][0] 0没有硬币时凑出总和 0使用的硬币数为 0其余f[0][x] INF凑出其他总和的方案不存在。由于求的是「最少」硬币数量无效值不应参与转移因此可设INF INT_MAX数学上的正无穷。3.3 朴素转移方程对于第 i 个硬币面值val有两种决策不使用该硬币f[i][j] f[i-1][j]使用该硬币由于每种硬币可被选择多次容量允许的前提下最优解为所有选择次数下的最小值f[i][j] min( f[i-1][j-k*val] k )其中 1 k 且 k*val j仓库中的朴素实现见 322. 零钱兑换中等.mdclass Solution { int INF Integer.MAX_VALUE; public int coinChange(int[] cs, int cnt) { int n cs.length; int[][] f new int[n 1][cnt 1]; // 初始化不考虑任何硬币时只有 f[0][0] 0其余均为无效值 for (int i 1; i cnt; i) f[0][i] INF; for (int i 1; i n; i) { int val cs[i - 1]; for (int j 0; j cnt; j) { // 不考虑当前硬币 f[i][j] f[i - 1][j]; // 考虑当前硬币可选个数由当前容量决定 for (int k 1; k * val j; k) { if (f[i - 1][j - k * val] ! INF) { f[i][j] Math.min(f[i][j], f[i-1][j-k*val] k); } } } } return f[n][cnt] INF ? -1 : f[n][cnt]; } }时间复杂度共有n * cnt个状态需要转移每个状态最多遍历cnt次整体为O(n * cnt²)空间复杂度O(n * cnt)。3.4 深入无效状态INF的定义艺术这是仓库题解中一个非常有价值的工程细节。在「取最小值」的转移中我们希望无效值无法凑出的总和不参与转移因此INF应代表正无穷。但如果直接使用INT_MAX作为INF一旦在其基础上累加如f[i-1][j-k*val] k常规语言中整数会溢出变成负的最小值丢失「正无穷」的语义——这与数学上正无穷可累加的概念相冲突。因此朴素解法中出现了「先判断再使用」的模式if (f[i-1][j] ! INF) { f[i][j] Math.min(f[i][j], f[i-1][j]); }每次使用都前置判断很麻烦更优雅的工程技巧是使用一个比INT_MAX小的较大数作为INF为累加预留空间。例如0x3f3f3f3f约 10.6 亿它足够大以表示「正无穷」又远小于INT_MAX约 21.4 亿即使累加若干次也不会溢出从而省去所有前置判断class Solution { int INF 0x3f3f3f3f; public int coinChange(int[] cs, int cnt) { int n cs.length; int[][] f new int[n 1][cnt 1]; for (int i 1; i cnt; i) f[0][i] INF; for (int i 1; i n; i) { int val cs[i - 1]; for (int j 0; j cnt; j) { f[i][j] f[i-1][j]; for (int k 0; k * val j; k) { f[i][j] Math.min(f[i][j], f[i-1][j-k*val] k); } } } return f[n][cnt] INF ? -1 : f[n][cnt]; } }这个0x3f3f3f3f约定在仓库的 279、322 等多篇题解中一致使用可以作为固定模板参数记忆。3.5 完全背包的一维空间优化站在「换元法」的高度朴素的 O(n * cnt²) 在amount较大时会超时需要做空间优化。仓库题解提供了一个比逐行数学推导更高效的理解角度——抽象「成本」与「价值」结合换元法。已知传统的完全背包二维转移方程f[i][j] max( f[i-1][j], f[i-1][j-k*w[i]] k*v[i] )经过严格证明的一维优化形式容量维度从小到大遍历f[j] max( f[j], f[j-w[i]] v[i] )回到本题朴素状态转移方程为f[i][j] min( f[i-1][j], f[i-1][j-k*coin] k )将硬币面值抽象为「成本」、硬币数量抽象为「价值」消除物品维度即得f[j] min( f[j], f[j-coin] 1 )仓库中的一维优化实现class Solution { int INF 0x3f3f3f3f; public int coinChange(int[] cs, int cnt) { int n cs.length; int[] f new int[cnt 1]; for (int i 1; i cnt; i) f[i] INF; for (int i 1; i n; i) { int val cs[i - 1]; for (int j val; j cnt; j) { f[j] Math.min(f[j], f[j - val] 1); } } return f[cnt] INF ? -1 : f[cnt]; } }时间复杂度O(n * cnt)空间复杂度O(cnt)。关键记忆点完全背包的一维优化容量维度必须「从小到大」遍历正序因为每种物品可取无限次正序遍历恰好允许同一物品在本轮被重复利用而 01 背包的一维优化必须「从大到小」遍历倒序以保证每件物品至多被取一次。这一正一反的对比在下文的 416 题中会再次出现。3.6 同模型延伸279. 完全平方数完全平方数中等.md 是同一模型的最小改动版本预处理出所有不超过 n 的完全平方数[1, 4, 9, ...]作为「物品」每个数字可使用无限次求凑出 n 所需的最少数字个数。状态定义、初始化f[0][0]0、其余INF与转移方程与 322 完全一致只是物品集合由「硬币面额」换成了「完全平方数」可视为对 322 模板的「换汤不换药」验证。四、01 背包实战416. 分割等和子集上下两篇4.1 题目与模型判别给你一个只包含正整数的非空数组nums判断是否可以将数组分割成两个子集使得两个子集的元素和相等。约束1 nums.length 2001 nums[i] 100。要分成两个元素和相等的子集等价于能否选出若干元素使其总和恰好为数组总和的一半记target sum / 2。每个元素至多选一次属于01 背包且只问「能否」属于「恰好型」布尔判定问题。4.2 上篇将「间接求解」转为「直接求解」仓库题解上416. 分割等和子集中等(上).md.md) 讲的是 01 背包的基础推导先以「总和不超过 j 的最大价值」这种经典间接状态入手再论证如何调整。题解下416. 分割等和子集中等(下).md.md) 则完成了关键的一步——修改状态定义使其与答案直接相关原定义f[i][j]代表考虑前 i 个数值、选择总和不超过 j 的最大价值新定义f[i][j]代表考虑前 i 个数值、选择总和是否恰好为 j布尔类型。对应转移方程∨为逻辑或f[i][j] f[i-1][j] ∨ f[i-1][j-nums[i]]含义想要「考虑前 i 个数值且总和恰好为 j」为真需要下列两种方案至少一种为真不选第 i 件物品f[i-1][j]为 true选第 i 件物品f[i-1][j-nums[i]]为 true。4.3 修改状态定义后的「初始化」陷阱仓库题解特别强调修改了状态定义之后除了调整转移方程还必须重新设计初始化。布尔数组初始值全为 false若不注入有效值递推将永远无法产生 true。通常使用「首行」来初始化有效值并配合「哨兵」思想将物品编号从 0 调整为从 1 开始让f[0][x]代表「不考虑任何物品」的情况于是f[0][0] true作为唯一有效起点完美规避了「第一个物品过大、永远装不进背包」的边界问题。完整常规解法见题解下篇class Solution { public boolean canPartition(int[] nums) { int n nums.length; //「等和子集」的和必然是总和的一半 int sum 0; for (int i : nums) sum i; int target sum / 2; // 总和为奇数时注定无法分为两个等和子集 if (target * 2 ! sum) return false; // f[i][j] 代表考虑前 i 件物品能否凑出价值「恰好」为 j 的方案 boolean[][] f new boolean[n1][target1]; f[0][0] true; for (int i 1; i n; i) { int t nums[i-1]; for (int j 0; j target; j) { // 不选该物品 boolean no f[i-1][j]; // 选该物品 boolean yes j t ? f[i-1][j-t] : false; f[i][j] no | yes; } } return f[n][target]; } }时间复杂度O(n * target)空间复杂度O(n * target)。4.4 滚动数组优化压缩物品维度滚动数组将物品维度压缩为 2用i 1在两层之间交替空间复杂度降为O(target)class Solution { public boolean canPartition(int[] nums) { int n nums.length; int sum 0; for (int i : nums) sum i; int target sum / 2; if (target * 2 ! sum) return false; // 修改「物品维度」为 2 boolean[][] f new boolean[2][target1]; f[0][0] true; for (int i 1; i n; i) { int t nums[i-1]; for (int j 0; j target; j) { boolean no f[(i-1)1][j]; boolean yes j t ? f[(i-1)1][j-t] : false; f[i1][j] no | yes; } } return f[n1][target]; } }4.5 一维空间优化01 背包必须「从大到小」遍历与完全背包正序相反01 背包的一维优化必须倒序遍历容量以保证每件物品至多被取一次正序会导致同一物品被重复选取退化为完全背包class Solution { public boolean canPartition(int[] nums) { int n nums.length; int sum 0; for (int i : nums) sum i; int target sum / 2; if (target * 2 ! sum) return false; // 取消「物品维度」 boolean[] f new boolean[target1]; f[0] true; for (int i 1; i n; i) { int t nums[i-1]; for (int j target; j 0; j--) { boolean no f[j]; boolean yes j t ? f[j-t] : false; f[j] no | yes; } } return f[target]; } }4.6 进阶变形1049. 最后一块石头的重量 II最后一块石头的重量 II中等.md 是 416 的隐藏变体每次选两块石头相撞等价于给每块石头赋予正负号问题转化为「将石头分成两组求两组总和之差的最小值」即 01 背包求「不超过 sum/2 的最大可达值」。理解了 416 的「恰好型」状态就能自然迁移到「不超过型」状态属于对同一模型的二次应用。五、一题多解示范494. 目标和给定非负整数数组nums和目标整数target向每个整数前添加或-求可以凑成目标和的表达式数目。仓库题解 494. 目标和中等.md 提供了完整的「一题四解」路线DFS → 记忆化搜索 → 01 背包展示了同一问题在不同算法视角下的演进。5.1 解法一DFS 爆搜数据范围只有 20每个数只有/-两种选择可直接 DFSclass Solution { public int findTargetSumWays(int[] nums, int t) { return dfs(nums, t, 0, 0); } int dfs(int[] nums, int t, int u, int cur) { if (u nums.length) { return cur t ? 1 : 0; } int left dfs(nums, t, u 1, cur nums[u]); int right dfs(nums, t, u 1, cur - nums[u]); return left right; } }时间复杂度O(2^n)。5.2 解法二记忆化搜索DFS 的可变参数只有「下标 u」和「当前结果 cur」可作记忆化容器的两个维度由于cur可能为负仓库实现选用哈希表存储class Solution { public int findTargetSumWays(int[] nums, int t) { return dfs(nums, t, 0, 0); } MapString, Integer cache new HashMap(); int dfs(int[] nums, int t, int u, int cur) { String key u _ cur; if (cache.containsKey(key)) return cache.get(key); if (u nums.length) { cache.put(key, cur t ? 1 : 0); return cache.get(key); } int left dfs(nums, t, u 1, cur nums[u]); int right dfs(nums, t, u 1, cur - nums[u]); cache.put(key, left right); return cache.get(key); } }时间复杂度O(n * Σ|nums[i]|)。5.3 解法三转化为 01 背包记忆化搜索的本质已经接近动态规划。令sum Σnums[i]设取的元素和为p则取-的元素和为sum - p目标target p - (sum - p)解得p (sum target) / 2需满足sum target为偶数且不小于 0。于是问题转化为从数组中选出若干元素、使其和恰好为 p 的方案数——标准的 01 背包「恰好型方案数」问题初始化f[0] 1、其余为 0。这再次印证了「识别背包模型」的核心能力先把题目改写为背包的标准形式再套用模板。六、完全背包求方案数518. 零钱兑换 II给定不同面额的硬币和一个总金额计算可以凑成总金额的硬币组合数每种硬币数量无限。仓库题解 518. 零钱兑换 II中等.md 指出322 求「最少物品个数」本题求「凑出特定价值的方案数量」求的东西不同但问题本质没有变同样属于组合优化问题。状态定义微调为f[i][j]为考虑前 i 件物品、凑成总和为 j 的方案数量。初始化f[0][0] 1不选任何硬币凑出 0方案数为 1其余f[0][x] 0。朴素转移k 表示选 k 个第 i 种硬币f[i][j] f[i-1][j] Σ f[i-1][j-k*val]其中 1 k ⌊j/val⌋朴素实现class Solution { public int change(int cnt, int[] cs) { int n cs.length; int[][] f new int[n 1][cnt 1]; f[0][0] 1; for (int i 1; i n; i) { int val cs[i - 1]; for (int j 0; j cnt; j) { f[i][j] f[i - 1][j]; for (int k 1; k * val j; k) { f[i][j] f[i - 1][j - k * val]; } } } return f[n][cnt]; } }同样可套用完全背包一维优化容量正序遍历得到f[j] f[j] f[j-val]的简洁形式。注意这里求的是「组合数」若求「排列数」如爬楼梯类问题则需调整遍历顺序题解中对此有细致区分。七、多维背包与分组背包进阶7.1 多维背包474. 一和零一和零中等.md 中每个字符串物品同时消耗「0 的个数」与「1 的个数」两个资源因此状态从一维容量扩展为二维f[i][j][k]代表考虑前 i 个字符串、消耗不超过 j 个 0 和 k 个 1 时能选取的最大字符串数量。这展示了背包容量维度可以不止一个转移时只需对每个资源维度分别做 01 背包的容量判断与倒序更新即可。7.2 分组背包与多维约束879. 盈利计划、1155. 掷骰子盈利计划困难.md 是「特殊多维背包」每项工作消耗成员数并产生利润需同时满足「成员不超过 n」与「利润不少于 minProfit」两个约束属于带双向约束的 01 背包变形难度为困难。掷骰子的N种方法中等.md 则可抽象为分组背包n 个骰子等价于 n 组每组每个骰子必须且只能选一个点数1~f求各点数之和恰好为 target 的方案数。仓库中另有同题副本文件内容一致可对照阅读。7.3 背包思想的延伸应用背包模型的边界非常宽泛仓库中还有大量「披着其他外衣」的背包题1449. 数位成本和为目标值的最大数字困难数字 0~9 各有成本求成本总和恰好为 target 时能拼出的最大数字是「恰好型完全背包 字典序贪心」的结合见 题解1995. 统计特殊四元组简单虽然是简单题但题解给出了「枚举 哈希」「DP」等多条路径其中 DP 视角可视为对「子集和」思想的轻量应用见 题解638. 大礼包中等混合了「完全背包」与「状态压缩」思想仓库 LeetCode/631-640/ 目录下有完整题解。八、背包 DP 解题模板与速查表综合仓库多篇题解可沉淀出如下可复用的解题流程8.1 四步解题流水线判别模型物品选择次数至多一次 → 01无限次 → 完全每组至多一个 → 分组 容量维度个数多维背包设计状态f[i][j]第一维为物品编号第二维为容量明确是「不超过 j」「恰好为 j」还是「至少为 j」这决定了初始化与最终答案的取法推导转移对每个物品写出「不选」与「选 k 个」的候选取最值或求和空间优化先滚动数组再一维化01 背包容量倒序完全背包容量正序。8.2 关键参数与边界速查要素01 背包恰好型完全背包最少数量完全背包方案数状态定义f[j]能否恰好凑出 jf[j]凑出 j 的最少个数f[j]凑出 j 的方案数初始化f[0]true其余 falsef[0]0其余INF(0x3f3f3f3f)f[0]1其余 0转移f[j] f[j] \| f[j-w]f[j] min(f[j], f[j-w]1)f[j] f[j] f[j-w]容量遍历倒序正序正序答案位置f[target]f[target] INF ? -1 : f[target]f[target]九、如何在仓库中系统学习与验证LogicStack-LeetCode 仓库以「日更题解」方式沉淀了完整的刷题系列见 README.md背包 DP 专题可从以下入口进入索引入口先读 Index/背包 DP.md按推荐指数 数量规划学习顺序从 4 星基础题入手再挑战 5 星进阶题成对阅读416 题分上、下两篇务必按顺序阅读——上篇讲「间接求解」与 01 背包基础下篇讲「直接求解」的状态重构与三种空间优化是理解「修改状态定义必须同步修改初始化」这一核心思想的最佳素材代码验证每篇题解的 Java 代码均可直接复制到 LeetCode 提交验证关注INF 0x3f3f3f3f、滚动数组i 1、容量正序/倒序这三个「模板关键点」对照本文速查表逐一确认举一反三用 322求最少与 518求方案数对照理解「同一模型、不同目标」用 416 与 494 对照理解「布尔判定」与「方案计数」的状态差异。背包问题的价值不在于背模板而在于建立「识别组合优化 → 匹配背包模型」的思维反射。当你看到「给定若干物品选择以达到某目标」时脑海中应自动弹出这套框架——这也是仓库中 322、416、518 等多篇题解反复强调的核心能力。将本文速查表与仓库题解结合使用即可系统性掌握从 01 背包到多维背包的完整知识体系。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐如何快速掌握背包问题01背包与完全背包变种详解如何快速掌握背包问题01背包与完全背包变种详解 背包问题是动态规划中的经典题型掌握它能帮助你轻松应对各类资源分配问题。本文将通过通俗易懂的方式带你从基础的文档教程知识库背包问题进阶指南混合背包、分组背包与二维费用背包的动态规划解法AlgoNote背包问题进阶指南混合背包、分组背包与二维费用背包的动态规划解法AlgoNote 本篇技术指南以「算法通关手册」AlgoNote 仓库的 08_09_kna教程文档知识库LeetCode-Go 题解 | 474. Ones and Zeroes二维 01 背包问题的 Go 实现LeetCode Go 题解 | 474. Ones and Zeroes二维 01 背包问题的 Go 实现 导读 本文以 LeetCode 第 474 题示例工程上一篇快速上手Hy-MT2-1.8B-FP85分钟完成多语言翻译模型部署下一篇Vulkan项目常见问题解决方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载导读背包问题Knapsack Problem是动态规划中最经典、最核心的模型之一也是面试与竞赛中出现频率极高的考点。本指南以 LogicStack-LeetCode 仓库的 Index/背包 DP.md 索引为核心骨架结合仓库内 279、322、416、494、518、879 等题目的完整题解源码系统讲解「01 背包」「完全背包」「多维背包」「分组背包」等子模型的判别方法、状态定义、状态转移方程、滚动数组与一维空间优化技巧。读完本文你将掌握一套「识别背包模型 → 设计状态 → 推导转移 → 优化空间」的通用解题流水线并能直接对照仓库中每道题的 Java 实现进行验证与练习。一、背包问题一套可以复用的动态规划框架1.1 什么是背包问题背包问题的本质是一个组合优化问题给定若干「物品」每个物品有体积成本和价值收益要求在不超出背包容量的前提下通过选择物品达到「全局最优」最大价值 / 最小成本或「特定状态」恰好凑出某个值 / 凑出某个值的方案数。仓库题解中反复强调的一个判别习惯是见 322. 零钱兑换中等.md当看到题目是给定一些「物品」让我们从中进行选择以达到「最大价值」或者「特定价值」时我们应该联想到「背包问题」。被选物品之间不需要满足特定关系只需要选择物品以达到「全局最优」或者「特定状态」即可。1.2 如何根据「选择次数限制」判别背包子模型拿到一道题先回答三个问题判别维度01 背包完全背包多维背包分组背包每种物品可选次数至多 1 次无限次至多 1 次每组至多选 1 个容量维度个数1 个1 个2 个及以上1 个典型题416、494322、518、2794740 和 1 两个维度1155骰子分组仓库中 416. 分割等和子集中等(上).md.md) 将背包模型做了系统总结而 322、518、279 三题则分别演示了完全背包在「求最少物品数」「求方案数」「求最少物品数」三个场景下的变形。下文将以这些仓库源码为实例逐步展开。二、题目索引仓库「背包 DP」专题完整清单以下是 LogicStack-LeetCode 仓库 Index/背包 DP.md 收录的全部背包类题目难度与推荐指数沿用索引原文题解列已转换为仓库内相对路径便于直接查阅题目仓库题解难度推荐指数279. 完全平方数题解中等322. 零钱兑换题解中等416. 分割等和子集上题解上.md)中等416. 分割等和子集下题解下.md)中等474. 一和零题解中等494. 目标和题解中等518. 零钱兑换 II题解中等638. 大礼包仓库 LeetCode/631-640/ 目录下中等879. 盈利计划题解困难1049. 最后一块石头的重量 II题解中等1155. 掷骰子的N种方法题解中等1449. 数位成本和为目标值的最大数字题解困难1995. 统计特殊四元组题解简单从「简单 → 中等 → 困难」的难度梯度可以看出背包模型可以覆盖从入门到进阶的完整链路而 416 上下两篇则专门用于精讲 01 背包从「间接求解」到「直接求解」的思维转换是仓库中背包系列的核心篇章。三、完全背包实战322. 零钱兑换3.1 题目与背包模型判别给定不同面额的硬币coins和一个总金额amount编写一个函数计算凑成总金额所需的最少硬币个数若无任何硬币组合能组成总金额返回-1。每种硬币数量无限。约束1 coins.length 121 coins[i] 2^31 - 10 amount 10^4。硬币相当于物品每种硬币可选择无限次因此属于完全背包目标是最小化「使用的硬币个数」。3.2 状态定义与初始化完全背包的原始状态定义是两维的第一维i代表物品编号前 i 件物品第二维j代表容量背包容量 / 目标总和。定义f[i][j]为考虑前 i 件物品、凑成总和为 j 所需要的最少硬币数量。初始化时引入「哨兵」思想令f[0][x]代表「不考虑任何物品」的情况于是f[0][0] 0没有硬币时凑出总和 0使用的硬币数为 0其余f[0][x] INF凑出其他总和的方案不存在。由于求的是「最少」硬币数量无效值不应参与转移因此可设INF INT_MAX数学上的正无穷。3.3 朴素转移方程对于第 i 个硬币面值val有两种决策不使用该硬币f[i][j] f[i-1][j]使用该硬币由于每种硬币可被选择多次容量允许的前提下最优解为所有选择次数下的最小值f[i][j] min( f[i-1][j-k*val] k )其中 1 k 且 k*val j仓库中的朴素实现见 322. 零钱兑换中等.mdclass Solution { int INF Integer.MAX_VALUE; public int coinChange(int[] cs, int cnt) { int n cs.length; int[][] f new int[n 1][cnt 1]; // 初始化不考虑任何硬币时只有 f[0][0] 0其余均为无效值 for (int i 1; i cnt; i) f[0][i] INF; for (int i 1; i n; i) { int val cs[i - 1]; for (int j 0; j cnt; j) { // 不考虑当前硬币 f[i][j] f[i - 1][j]; // 考虑当前硬币可选个数由当前容量决定 for (int k 1; k * val j; k) { if (f[i - 1][j - k * val] ! INF) { f[i][j] Math.min(f[i][j], f[i-1][j-k*val] k); } } } } return f[n][cnt] INF ? -1 : f[n][cnt]; } }时间复杂度共有n * cnt个状态需要转移每个状态最多遍历cnt次整体为O(n * cnt²)空间复杂度O(n * cnt)。3.4 深入无效状态INF的定义艺术这是仓库题解中一个非常有价值的工程细节。在「取最小值」的转移中我们希望无效值无法凑出的总和不参与转移因此INF应代表正无穷。但如果直接使用INT_MAX作为INF一旦在其基础上累加如f[i-1][j-k*val] k常规语言中整数会溢出变成负的最小值丢失「正无穷」的语义——这与数学上正无穷可累加的概念相冲突。因此朴素解法中出现了「先判断再使用」的模式if (f[i-1][j] ! INF) { f[i][j] Math.min(f[i][j], f[i-1][j]); }每次使用都前置判断很麻烦更优雅的工程技巧是使用一个比INT_MAX小的较大数作为INF为累加预留空间。例如0x3f3f3f3f约 10.6 亿它足够大以表示「正无穷」又远小于INT_MAX约 21.4 亿即使累加若干次也不会溢出从而省去所有前置判断class Solution { int INF 0x3f3f3f3f; public int coinChange(int[] cs, int cnt) { int n cs.length; int[][] f new int[n 1][cnt 1]; for (int i 1; i cnt; i) f[0][i] INF; for (int i 1; i n; i) { int val cs[i - 1]; for (int j 0; j cnt; j) { f[i][j] f[i-1][j]; for (int k 0; k * val j; k) { f[i][j] Math.min(f[i][j], f[i-1][j-k*val] k); } } } return f[n][cnt] INF ? -1 : f[n][cnt]; } }这个0x3f3f3f3f约定在仓库的 279、322 等多篇题解中一致使用可以作为固定模板参数记忆。3.5 完全背包的一维空间优化站在「换元法」的高度朴素的 O(n * cnt²) 在amount较大时会超时需要做空间优化。仓库题解提供了一个比逐行数学推导更高效的理解角度——抽象「成本」与「价值」结合换元法。已知传统的完全背包二维转移方程f[i][j] max( f[i-1][j], f[i-1][j-k*w[i]] k*v[i] )经过严格证明的一维优化形式容量维度从小到大遍历f[j] max( f[j], f[j-w[i]] v[i] )回到本题朴素状态转移方程为f[i][j] min( f[i-1][j], f[i-1][j-k*coin] k )将硬币面值抽象为「成本」、硬币数量抽象为「价值」消除物品维度即得f[j] min( f[j], f[j-coin] 1 )仓库中的一维优化实现class Solution { int INF 0x3f3f3f3f; public int coinChange(int[] cs, int cnt) { int n cs.length; int[] f new int[cnt 1]; for (int i 1; i cnt; i) f[i] INF; for (int i 1; i n; i) { int val cs[i - 1]; for (int j val; j cnt; j) { f[j] Math.min(f[j], f[j - val] 1); } } return f[cnt] INF ? -1 : f[cnt]; } }时间复杂度O(n * cnt)空间复杂度O(cnt)。关键记忆点完全背包的一维优化容量维度必须「从小到大」遍历正序因为每种物品可取无限次正序遍历恰好允许同一物品在本轮被重复利用而 01 背包的一维优化必须「从大到小」遍历倒序以保证每件物品至多被取一次。这一正一反的对比在下文的 416 题中会再次出现。3.6 同模型延伸279. 完全平方数完全平方数中等.md 是同一模型的最小改动版本预处理出所有不超过 n 的完全平方数[1, 4, 9, ...]作为「物品」每个数字可使用无限次求凑出 n 所需的最少数字个数。状态定义、初始化f[0][0]0、其余INF与转移方程与 322 完全一致只是物品集合由「硬币面额」换成了「完全平方数」可视为对 322 模板的「换汤不换药」验证。四、01 背包实战416. 分割等和子集上下两篇4.1 题目与模型判别给你一个只包含正整数的非空数组nums判断是否可以将数组分割成两个子集使得两个子集的元素和相等。约束1 nums.length 2001 nums[i] 100。要分成两个元素和相等的子集等价于能否选出若干元素使其总和恰好为数组总和的一半记target sum / 2。每个元素至多选一次属于01 背包且只问「能否」属于「恰好型」布尔判定问题。4.2 上篇将「间接求解」转为「直接求解」仓库题解上416. 分割等和子集中等(上).md.md) 讲的是 01 背包的基础推导先以「总和不超过 j 的最大价值」这种经典间接状态入手再论证如何调整。题解下416. 分割等和子集中等(下).md.md) 则完成了关键的一步——修改状态定义使其与答案直接相关原定义f[i][j]代表考虑前 i 个数值、选择总和不超过 j 的最大价值新定义f[i][j]代表考虑前 i 个数值、选择总和是否恰好为 j布尔类型。对应转移方程∨为逻辑或f[i][j] f[i-1][j] ∨ f[i-1][j-nums[i]]含义想要「考虑前 i 个数值且总和恰好为 j」为真需要下列两种方案至少一种为真不选第 i 件物品f[i-1][j]为 true选第 i 件物品f[i-1][j-nums[i]]为 true。4.3 修改状态定义后的「初始化」陷阱仓库题解特别强调修改了状态定义之后除了调整转移方程还必须重新设计初始化。布尔数组初始值全为 false若不注入有效值递推将永远无法产生 true。通常使用「首行」来初始化有效值并配合「哨兵」思想将物品编号从 0 调整为从 1 开始让f[0][x]代表「不考虑任何物品」的情况于是f[0][0] true作为唯一有效起点完美规避了「第一个物品过大、永远装不进背包」的边界问题。完整常规解法见题解下篇class Solution { public boolean canPartition(int[] nums) { int n nums.length; //「等和子集」的和必然是总和的一半 int sum 0; for (int i : nums) sum i; int target sum / 2; // 总和为奇数时注定无法分为两个等和子集 if (target * 2 ! sum) return false; // f[i][j] 代表考虑前 i 件物品能否凑出价值「恰好」为 j 的方案 boolean[][] f new boolean[n1][target1]; f[0][0] true; for (int i 1; i n; i) { int t nums[i-1]; for (int j 0; j target; j) { // 不选该物品 boolean no f[i-1][j]; // 选该物品 boolean yes j t ? f[i-1][j-t] : false; f[i][j] no | yes; } } return f[n][target]; } }时间复杂度O(n * target)空间复杂度O(n * target)。4.4 滚动数组优化压缩物品维度滚动数组将物品维度压缩为 2用i 1在两层之间交替空间复杂度降为O(target)class Solution { public boolean canPartition(int[] nums) { int n nums.length; int sum 0; for (int i : nums) sum i; int target sum / 2; if (target * 2 ! sum) return false; // 修改「物品维度」为 2 boolean[][] f new boolean[2][target1]; f[0][0] true; for (int i 1; i n; i) { int t nums[i-1]; for (int j 0; j target; j) { boolean no f[(i-1)1][j]; boolean yes j t ? f[(i-1)1][j-t] : false; f[i1][j] no | yes; } } return f[n1][target]; } }4.5 一维空间优化01 背包必须「从大到小」遍历与完全背包正序相反01 背包的一维优化必须倒序遍历容量以保证每件物品至多被取一次正序会导致同一物品被重复选取退化为完全背包class Solution { public boolean canPartition(int[] nums) { int n nums.length; int sum 0; for (int i : nums) sum i; int target sum / 2; if (target * 2 ! sum) return false; // 取消「物品维度」 boolean[] f new boolean[target1]; f[0] true; for (int i 1; i n; i) { int t nums[i-1]; for (int j target; j 0; j--) { boolean no f[j]; boolean yes j t ? f[j-t] : false; f[j] no | yes; } } return f[target]; } }4.6 进阶变形1049. 最后一块石头的重量 II最后一块石头的重量 II中等.md 是 416 的隐藏变体每次选两块石头相撞等价于给每块石头赋予正负号问题转化为「将石头分成两组求两组总和之差的最小值」即 01 背包求「不超过 sum/2 的最大可达值」。理解了 416 的「恰好型」状态就能自然迁移到「不超过型」状态属于对同一模型的二次应用。五、一题多解示范494. 目标和给定非负整数数组nums和目标整数target向每个整数前添加或-求可以凑成目标和的表达式数目。仓库题解 494. 目标和中等.md 提供了完整的「一题四解」路线DFS → 记忆化搜索 → 01 背包展示了同一问题在不同算法视角下的演进。5.1 解法一DFS 爆搜数据范围只有 20每个数只有/-两种选择可直接 DFSclass Solution { public int findTargetSumWays(int[] nums, int t) { return dfs(nums, t, 0, 0); } int dfs(int[] nums, int t, int u, int cur) { if (u nums.length) { return cur t ? 1 : 0; } int left dfs(nums, t, u 1, cur nums[u]); int right dfs(nums, t, u 1, cur - nums[u]); return left right; } }时间复杂度O(2^n)。5.2 解法二记忆化搜索DFS 的可变参数只有「下标 u」和「当前结果 cur」可作记忆化容器的两个维度由于cur可能为负仓库实现选用哈希表存储class Solution { public int findTargetSumWays(int[] nums, int t) { return dfs(nums, t, 0, 0); } MapString, Integer cache new HashMap(); int dfs(int[] nums, int t, int u, int cur) { String key u _ cur; if (cache.containsKey(key)) return cache.get(key); if (u nums.length) { cache.put(key, cur t ? 1 : 0); return cache.get(key); } int left dfs(nums, t, u 1, cur nums[u]); int right dfs(nums, t, u 1, cur - nums[u]); cache.put(key, left right); return cache.get(key); } }时间复杂度O(n * Σ|nums[i]|)。5.3 解法三转化为 01 背包记忆化搜索的本质已经接近动态规划。令sum Σnums[i]设取的元素和为p则取-的元素和为sum - p目标target p - (sum - p)解得p (sum target) / 2需满足sum target为偶数且不小于 0。于是问题转化为从数组中选出若干元素、使其和恰好为 p 的方案数——标准的 01 背包「恰好型方案数」问题初始化f[0] 1、其余为 0。这再次印证了「识别背包模型」的核心能力先把题目改写为背包的标准形式再套用模板。六、完全背包求方案数518. 零钱兑换 II给定不同面额的硬币和一个总金额计算可以凑成总金额的硬币组合数每种硬币数量无限。仓库题解 518. 零钱兑换 II中等.md 指出322 求「最少物品个数」本题求「凑出特定价值的方案数量」求的东西不同但问题本质没有变同样属于组合优化问题。状态定义微调为f[i][j]为考虑前 i 件物品、凑成总和为 j 的方案数量。初始化f[0][0] 1不选任何硬币凑出 0方案数为 1其余f[0][x] 0。朴素转移k 表示选 k 个第 i 种硬币f[i][j] f[i-1][j] Σ f[i-1][j-k*val]其中 1 k ⌊j/val⌋朴素实现class Solution { public int change(int cnt, int[] cs) { int n cs.length; int[][] f new int[n 1][cnt 1]; f[0][0] 1; for (int i 1; i n; i) { int val cs[i - 1]; for (int j 0; j cnt; j) { f[i][j] f[i - 1][j]; for (int k 1; k * val j; k) { f[i][j] f[i - 1][j - k * val]; } } } return f[n][cnt]; } }同样可套用完全背包一维优化容量正序遍历得到f[j] f[j] f[j-val]的简洁形式。注意这里求的是「组合数」若求「排列数」如爬楼梯类问题则需调整遍历顺序题解中对此有细致区分。七、多维背包与分组背包进阶7.1 多维背包474. 一和零一和零中等.md 中每个字符串物品同时消耗「0 的个数」与「1 的个数」两个资源因此状态从一维容量扩展为二维f[i][j][k]代表考虑前 i 个字符串、消耗不超过 j 个 0 和 k 个 1 时能选取的最大字符串数量。这展示了背包容量维度可以不止一个转移时只需对每个资源维度分别做 01 背包的容量判断与倒序更新即可。7.2 分组背包与多维约束879. 盈利计划、1155. 掷骰子盈利计划困难.md 是「特殊多维背包」每项工作消耗成员数并产生利润需同时满足「成员不超过 n」与「利润不少于 minProfit」两个约束属于带双向约束的 01 背包变形难度为困难。掷骰子的N种方法中等.md 则可抽象为分组背包n 个骰子等价于 n 组每组每个骰子必须且只能选一个点数1~f求各点数之和恰好为 target 的方案数。仓库中另有同题副本文件内容一致可对照阅读。7.3 背包思想的延伸应用背包模型的边界非常宽泛仓库中还有大量「披着其他外衣」的背包题1449. 数位成本和为目标值的最大数字困难数字 0~9 各有成本求成本总和恰好为 target 时能拼出的最大数字是「恰好型完全背包 字典序贪心」的结合见 题解1995. 统计特殊四元组简单虽然是简单题但题解给出了「枚举 哈希」「DP」等多条路径其中 DP 视角可视为对「子集和」思想的轻量应用见 题解638. 大礼包中等混合了「完全背包」与「状态压缩」思想仓库 LeetCode/631-640/ 目录下有完整题解。八、背包 DP 解题模板与速查表综合仓库多篇题解可沉淀出如下可复用的解题流程8.1 四步解题流水线判别模型物品选择次数至多一次 → 01无限次 → 完全每组至多一个 → 分组 容量维度个数多维背包设计状态f[i][j]第一维为物品编号第二维为容量明确是「不超过 j」「恰好为 j」还是「至少为 j」这决定了初始化与最终答案的取法推导转移对每个物品写出「不选」与「选 k 个」的候选取最值或求和空间优化先滚动数组再一维化01 背包容量倒序完全背包容量正序。8.2 关键参数与边界速查要素01 背包恰好型完全背包最少数量完全背包方案数状态定义f[j]能否恰好凑出 jf[j]凑出 j 的最少个数f[j]凑出 j 的方案数初始化f[0]true其余 falsef[0]0其余INF(0x3f3f3f3f)f[0]1其余 0转移f[j] f[j] \| f[j-w]f[j] min(f[j], f[j-w]1)f[j] f[j] f[j-w]容量遍历倒序正序正序答案位置f[target]f[target] INF ? -1 : f[target]f[target]九、如何在仓库中系统学习与验证LogicStack-LeetCode 仓库以「日更题解」方式沉淀了完整的刷题系列见 README.md背包 DP 专题可从以下入口进入索引入口先读 Index/背包 DP.md按推荐指数 数量规划学习顺序从 4 星基础题入手再挑战 5 星进阶题成对阅读416 题分上、下两篇务必按顺序阅读——上篇讲「间接求解」与 01 背包基础下篇讲「直接求解」的状态重构与三种空间优化是理解「修改状态定义必须同步修改初始化」这一核心思想的最佳素材代码验证每篇题解的 Java 代码均可直接复制到 LeetCode 提交验证关注INF 0x3f3f3f3f、滚动数组i 1、容量正序/倒序这三个「模板关键点」对照本文速查表逐一确认举一反三用 322求最少与 518求方案数对照理解「同一模型、不同目标」用 416 与 494 对照理解「布尔判定」与「方案计数」的状态差异。背包问题的价值不在于背模板而在于建立「识别组合优化 → 匹配背包模型」的思维反射。当你看到「给定若干物品选择以达到某目标」时脑海中应自动弹出这套框架——这也是仓库中 322、416、518 等多篇题解反复强调的核心能力。将本文速查表与仓库题解结合使用即可系统性掌握从 01 背包到多维背包的完整知识体系。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐如何快速掌握背包问题01背包与完全背包变种详解如何快速掌握背包问题01背包与完全背包变种详解 背包问题是动态规划中的经典题型掌握它能帮助你轻松应对各类资源分配问题。本文将通过通俗易懂的方式带你从基础的文档教程知识库背包问题进阶指南混合背包、分组背包与二维费用背包的动态规划解法AlgoNote背包问题进阶指南混合背包、分组背包与二维费用背包的动态规划解法AlgoNote 本篇技术指南以「算法通关手册」AlgoNote 仓库的 08_09_kna教程文档知识库LeetCode-Go 题解 | 474. Ones and Zeroes二维 01 背包问题的 Go 实现LeetCode Go 题解 | 474. Ones and Zeroes二维 01 背包问题的 Go 实现 导读 本文以 LeetCode 第 474 题示例工程上一篇快速上手Hy-MT2-1.8B-FP85分钟完成多语言翻译模型部署下一篇Vulkan项目常见问题解决方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
