高频必考！0-1背包：分割等和子集，一维优化为什么必须倒序？

用爬楼梯立起了DP五步曲。今天进入DP面试考查率最高的家族——背包问题。LC.416「分割等和子集」是0-1背包的经典入门题但它的杀伤力远超一道中等题面试官会盯着你的代码问一句——“一维优化时容量为什么必须倒序遍历正序到底会出什么事”这个问题答不上来说明你的一维背包只是背下来的答得上来面试官就知道你真懂 DP。 题目速览30秒读懂给你一个只含正整数的非空数组nums判断能否分割成两个元素和相等的子集。示例[1,5,11,5]→true分成[1,5,5]和[11]示例[2,2,3,5]→false约束n ≤ 200nums[i] ≤ 100。前置剪枝若sum为奇数直接返回false——两相等整数之和必为偶数。若为偶数问题变成能否从数组中选若干个数恰好凑出target sum/2。 核心思路识别背包 → 二维打底 → 一维提速暴力为什么不行每个数字有“选/不选”两种命运n200时组合数2^200暴力枚举子集等于自杀。识别背包这是0-1背包的“存在性”问题每个数字要么选、要么不选对单个子集而言→ 0-1背包指纹数字的值 重量 价值背包容量 target问的是“能否恰好装满”→ 存在性问题状态定义二维dp[i][j] 从前 i 个数字中能否选出若干个和恰好为 j布尔值。状态转移方程考虑第 i 个数字num不选它dp[i-1][j]选它前提j numdp[i-1][j-num]dp[i][j] dp[i-1][j] || (j num dp[i-1][j-num])初始化dp[0][0] true0个数字凑出0天然成立dp[0][j0] false一维优化核心是“倒序”观察转移方程第 i 行只依赖第i-1行——二维表可以压成一行dp[j]。但压行会引发一个致命问题覆盖。二维里dp[i][j]依赖的是上一行的dp[i-1][j-num]。压成一行后正序错误算dp[j]时dp[j-num]已被本轮更新成第i行的值——相当于“同一个数字被选了两次”悄悄变成完全背包。倒序正确先算大j它依赖的小j-num还没被动过依然是“上一行”的旧值。一句话记住倒序保证dp[j-num]永远是上一行的旧值每个物品恰好决策一次。️ 图解算法手把手走一遍nums [1, 5, 11, 5]sum 22target 11。二维 DP 表✓ truedp[i][j]j0j1j2…j5…j10j11i0无数字✓i11✓✓i25✓✓✓i311✓✓✓✓i45✓✓✓✓关键在第 4 行 j11选 11 →dp[3][0]true选 5 →dp[3][6]true15。两路皆通返回 true✅一维正序 vs 倒序num5演示正序错误示范j从1扫到 11j6: dp[6] ← dp[1] true 凑6 5 1合理 j10: dp[10] ← dp[5] true 但dp[5]是本轮刚更新的 → 相当于一个5被用了两次5510倒序正确j从11扫到1j11: dp[11] ← dp[6]旧值本轮尚未改动✓ j10: dp[10] ← dp[5]仍是上一行的旧值→ 用的是还没选过这个5的状态这五行的推导就是0-1背包与完全背包的分水岭。 代码实现Python Java二维 一维Python版classSolution:# 解法一二维DP defcanPartition2D(self,nums:List[int])-bool:totalsum(nums)iftotal%2:# 奇数和必不能平分returnFalsetargettotal//2nlen(nums)dp[[False]*(target1)for_inrange(n1)]dp[0][0]True# 0 个数字凑出 0foriinrange(1,n1):numnums[i-1]forjinrange(target1):dp[i][j]dp[i-1][j]# 不选 numifjnum:# 选 numdp[i][j]|dp[i-1][j-num]returndp[n][target]# 解法二一维优化倒序推荐 defcanPartition(self,nums:List[int])-bool:totalsum(nums)iftotal%2:returnFalsetargettotal//2dp[False]*(target1)dp[0]True# 容量0恒可达fornuminnums:# 外层物品forjinrange(target,num-1,-1):# 内层容量【倒序】dp[j]dp[j]ordp[j-num]# dp[j-num] 是上一行旧值returndp[target]Java版classSolution{// 解法一二维 DP publicbooleancanPartition2D(int[]nums){inttotal0;for(intx:nums)totalx;if(total%2!0)returnfalse;inttargettotal/2,nnums.length;boolean[][]dpnewboolean[n1][target1];dp[0][0]true;for(inti1;in;i){intnumnums[i-1];for(intj0;jtarget;j){dp[i][j]dp[i-1][j];if(jnum)dp[i][j]|dp[i-1][j-num];}}returndp[n][target];}// 解法二一维优化倒序推荐 publicbooleancanPartition(int[]nums){inttotal0;for(intx:nums)totalx;if(total%2!0)returnfalse;inttargettotal/2;boolean[]dpnewboolean[target1];dp[0]true;for(intnum:nums){// 外层物品for(intjtarget;jnum;j--){// 内层容量【倒序】dp[j]dp[j]||dp[j-num];}}returndp[target];}}⚠️致命坑必看一维优化时内层容量必须倒序——正序会让dp[j-num]混入本轮已选当前物品的脏数据。外层物品、内层容量顺序不能反。奇数和直接剪枝省一半时间。⏱️ 复杂度分析面试必问版本时间空间二维DPO(n × target)O(n × target)一维优化O(n × target)O(target)target sum/2。本题n ≤ 200、target ≤ 10000约200万次运算轻松通过。相比暴力O(2^n)这是DP的降维打击。 举一反三3 道高频变种题题目变化点思路调整LC.494 目标和每个数加 /- 使结果为S转化为求子集和为(sumS)/2的方案数一维倒序改计数dp[j] dp[j-num]LC.1049 最后一块石头的重量II两两相撞求最小剩余转化为容量sum/2的0-1背包求能装的最大和LC.698 划分为k个相等的子集分k份而非2份背包模型失效用状态压缩 回溯 面试追问模拟提前准备惊艳全场Q1一维为什么倒序正序会怎样正序时dp[j-num]在同一轮已被更新混入了“当前物品已选”的信息等于允许每件物品选无限次0-1背包悄悄变成完全背包可能凭空产出false→true的错误结论倒序保证用到的是上一行旧值每件物品恰好决策一次。Q2背包问题都能问什么经典四问①最大值容量内最大价值②最小值装满最少件数③存在性能否恰好装满如本题④方案数恰好装满有几种方式。四问共用“状态 物品 × 容量”的骨架只换转移算子max / min / or / 。Q3有没有更快的判定法存在性问题上界就是 O(n·target)但有bitset位优化把dp数组看成一个整数转移即bits | bits num利用机器字长64位并行理论复杂度除以64。Python 一行bits | bits num也极优雅。 实战小技巧刷题党必备口诀0-1背包倒序跑完全背包正序来物品外层容量内选与不选两条路。模板存在性dp[j] dp[j] || dp[j-num]方案数dp[j] dp[j-num]最值dp[j] max/min(dp[j], dp[j-num] val)。防坑一维优化内层倒序忘一次错一次。 实际应用场景不止是刷题资源分配服务器内存能否恰好切分满足两批任务打包装箱货物能否对半分给两辆车编译器寄存器分配简化模型NP-hard问题0-1背包是著名的“伪多项式可解”代表 今日思考题如果题目改成“能否分成两个子集使它们的差最小”你会怎么改提示转化为容量sum/2 的0-1背包求能装到的最大和答案 sum - 2 × 最大和。