高频必考！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 ≤ 200，nums[i] ≤ 100。

前置剪枝：

若sum为奇数，直接返回false——两相等整数之和必为偶数。

若为偶数，问题变成：能否从数组中选若干个数，恰好凑出target = sum/2。

🧠 核心思路：识别背包 → 二维打底 → 一维提速

暴力为什么不行？

每个数字有“选/不选”两种命运，n=200时组合数2^200，暴力枚举子集等于自杀。

识别背包：这是0-1背包的“存在性”问题

• 每个数字要么选、要么不选（对单个子集而言）→ 0-1背包指纹
• 数字的值 = 重量 = 价值
• 背包容量 = target
• 问的是“能否恰好装满”→ 存在性问题

状态定义（二维）

dp[i][j]= 从前 i 个数字中能否选出若干个，和恰好为 j（布尔值）。

状态转移方程

考虑第 i 个数字num：

• 不选它：dp[i-1][j]
• 选它（前提j >= num）：dp[i-1][j-num]

dp[i][j] = dp[i-1][j] || (j >= num && dp[i-1][j-num])

初始化

• dp[0][0] = true（0个数字凑出0，天然成立）
• dp[0][j>0] = 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 = 22，target = 11。二维 DP 表（✓ = true）：

关键在第 4 行 j=11：选 11 →dp[3][0]=true；选 5 →dp[3][6]=true（1+5）。两路皆通，返回 true✅

一维正序 vs 倒序（num=5演示）

正序（错误示范），j从1扫到 11：

j=6: dp[6] ← dp[1] = true （凑6 = 5 + 1，合理） j=10: dp[10] ← dp[5] = true （但dp[5]是本轮刚更新的！） → 相当于一个5被用了两次：5+5=10

倒序（正确），j从11扫到1：

j=11: dp[11] ← dp[6]（旧值，本轮尚未改动）✓ j=10: dp[10] ← dp[5]（仍是上一行的旧值）→ 用的是"还没选过这个5"的状态

这五行的推导，就是0-1背包与完全背包的分水岭。

💻 代码实现（Python + Java，二维 + 一维）

Python版

classSolution:# ===== 解法一：二维DP =====defcanPartition2D(self,nums:List[int])->bool:total=sum(nums)iftotal%2:# 奇数和必不能平分returnFalsetarget=total//2n=len(nums)dp=[[False]*(target+1)for_inrange(n+1)]dp[0][0]=True# 0 个数字凑出 0foriinrange(1,n+1):num=nums[i-1]forjinrange(target+1):dp[i][j]=dp[i-1][j]# 不选 numifj>=num:# 选 numdp[i][j]|=dp[i-1][j-num]returndp[n][target]# ===== 解法二：一维优化（倒序）推荐 =====defcanPartition(self,nums:List[int])->bool:total=sum(nums)iftotal%2:returnFalsetarget=total//2dp=[False]*(target+1)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){inttotal=0;for(intx:nums)total+=x;if(total%2!=0)returnfalse;inttarget=total/2,n=nums.length;boolean[][]dp=newboolean[n+1][target+1];dp[0][0]=true;for(inti=1;i<=n;i++){intnum=nums[i-1];for(intj=0;j<=target;j++){dp[i][j]=dp[i-1][j];if(j>=num)dp[i][j]|=dp[i-1][j-num];}}returndp[n][target];}// ===== 解法二：一维优化（倒序）推荐 =====publicbooleancanPartition(int[]nums){inttotal=0;for(intx:nums)total+=x;if(total%2!=0)returnfalse;inttarget=total/2;boolean[]dp=newboolean[target+1];dp[0]=true;for(intnum:nums){// 外层：物品for(intj=target;j>=num;j--){// 内层：容量【倒序】！dp[j]=dp[j]||dp[j-num];}}returndp[target];}}

⚠️致命坑（必看）：

• 一维优化时，内层容量必须倒序——正序会让dp[j-num]混入本轮已选当前物品的脏数据。
• 外层物品、内层容量，顺序不能反。
• 奇数和直接剪枝，省一半时间。

⏱️ 复杂度分析（面试必问）

target = sum/2。本题n ≤ 200、target ≤ 10000，约200万次运算，轻松通过。相比暴力O(2^n)，这是DP的降维打击。

🚀 举一反三：3 道高频变种题

💬 面试追问模拟（提前准备，惊艳全场）

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 × 最大和。