最后一块石头 II

最直接的想法：每块石头要么进左堆、要么进右堆，n 块就有 2ⁿ 种分法，逐一算两堆差再取最小。石头一多就算爆了，重复枚举太浪费。

设其中一堆和为 s，另一堆就是 total−s，差 = |total−2s|。s 越接近 total÷2，差越小。于是问题变成 0-1 背包：状态 dp[j]=容量 j 内子集和的最大值；转移 dp[j]=max(dp[j], dp[j−x]+x)，x 这块石头选或不选。容量上限取 total÷2=7。

1. 建表 · dp 是布尔可达表：表头是容量 0 到 7。dp[j] 记「能不能从石头里挑一个子集，正好凑出和 j」。一开始只有空集，和为 0,所以只有 dp[0]=✓,其余全是 ·(不可达)。下面一块块石头往里塞。

2. 转移方程 · 选或不选这块石头：每放一块石头 x,每个容量 j 有两种选择:不选 x(沿用旧 dp[j]),或选 x(看 dp[j-x] 是否可达)。两者只要有一个 ✓,dp[j] 就 ✓。关键:内层 j 倒着扫,保证 dp[j-x] 是「还没用这块 x」的旧值,每块石头只用一次。

3. 放石头 2 · 内层 j 从 7 倒扫到 2：放石头 2,内层容量从 7 倒着扫到 2。对每个 j,只要「不选 2 时已可达(dp[j])」或「dp[j-2] 可达再加上这块 2」,dp[j] 就变可达。容量 1 装不下 2,跳过。

4. 放石头 2 · dp[2] 变可达：看容量 2:dp[2-2]=dp[0]=✓,说明挑子集 {2} 正好凑出 2,所以 dp[2] 变成 ✓(可达)。

5. 放石头 2 · dp[3..7] 依旧不可达：容量 3 到 7 想靠石头 2 变可达,要看 dp[j-2]。但 dp[3]、dp[4]…对应的 dp[1]、dp[2](旧值)、dp[3]… 都还是 ·,所以这几格保持不可达。放完石头 2:只有 dp[0]、dp[2] 可达。

6. 放石头 7 · 只有容量 7 装得下：放石头 7:它本身就是 7,内层 j 从 7 倒扫,j 小于 7 都装不下,只有容量 7 能算。dp[7-7]=dp[0]=✓,于是 dp[7] 变可达(子集 {7})。

7. 放石头 7 · 容量小于 7 装不下：注意负例:容量 6 及更小想装石头 7,j-7 会变成负数,根本装不下。这些格子只能沿用「不选这块」的旧值,保持原状。这正是内层只倒扫到 x 的原因。放完石头 7:可达的是 dp[0]、dp[2]、dp[7]。

8. 放石头 4 · dp[6] 变可达：放石头 4,内层从 7 倒扫到 4。容量 6:dp[6-4]=dp[2]=✓(子集 {2} 再加这块 4),所以 dp[6] 变可达,对应子集 {2,4}=6。

9. 放石头 4 · dp[4] 变可达：继续扫:容量 4 看 dp[4-4]=dp[0]=✓,挑子集 {4} 正好凑 4,dp[4] 变可达。

10. 放石头 4 · dp[7]、dp[5] 不变：容量 7 看 dp[7-4]=dp[3]=·,加不上;但 dp[7] 本来就是 ✓,保持可达。容量 5 看 dp[5-4]=dp[1]=·,仍不可达。放完石头 4:可达的是 dp[0]、dp[2]、dp[4]、dp[6]、dp[7]。

11. 放石头 1 · dp[5] 变可达：放最后一块石头 1,内层从 7 倒扫到 1。容量 5:dp[5-1]=dp[4]=✓(子集 {4} 加这块 1),dp[5] 变可达,对应 {4,1}=5。

12. 放石头 1 · dp[3] 变可达：继续:容量 3 看 dp[3-1]=dp[2]=✓(子集 {2} 加这块 1),dp[3] 变可达,对应 {2,1}=3。倒序扫保证 dp[2] 用的是没放这块 1 时的旧值。

13. 放石头 1 · dp[1] 变可达, 全部填满：容量 1 看 dp[1-1]=dp[0]=✓(单独子集 {1}),dp[1] 变可达。至此四块石头都放完,dp[0] 到 dp[7] 全部可达——半容量内每个和都凑得出。

14. 找最大可达的一堆 · 从 7 往下：从容量上限 7 往下找第一个可达的格子:dp[7]=✓,说明在「不超过半和 7」的前提下,一堆能正好凑到 7(子集 {2,4,1})。这就是离半和最近的一堆。

15. 算答案 · total − 2×s：一堆是 7,另一堆 14−7=7,两堆差 = total − 2×7 = 0。这就是最后撞剩的最小重量,也就是答案 0。

以后看到「把数组分两堆、让两堆差最小」，一律转成背包：在 sum÷2 的容量里求最大子集和，差就是 sum − 2×它。和目标和、分割等和子集是同一个套路。