题目描述
每次拿两块石头相撞，剩下两者的重量差(相等就一起碎掉)，反复撞，求最后剩下的最小重量。
思路解析
最直接的想法：每块石头要么进左堆、要么进右堆，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。
建表 · dp[0]=0：表头是容量 0 到 7。dp[j] 表示「容量 j 内能装出的最大子集和」，全部先初始成 0（什么都不装，和为 0）。下面一块块石头往里塞。
放石头 2：放石头 2，内层从大到小扫容量：只要容量不小于 2，就能装下它，dp[j]=dp[j−2]+2=2。容量 2 到 7 全变成 2。容量 1 装不下，保持 0。
放石头 7 · 大格更新：放石头 7：只有容量正好 7 才装得下它。dp[7]=max(原来的 2, dp[0]+7)=7。现在容量 7 能装出和 7（就单独那块 7）。
放石头 7 · 装不下的格：注意负例：容量 6（以及更小）想装石头 7，j−7 会变成负数，根本装不下。这些格子只能沿用「不选这块石头」的旧值，dp[6] 还是 2。这就是循环只扫到 x 为止的原因。
放石头 4：放石头 4：容量 6 现在能装 {2,4}=6（dp[2]+4）；容量 5、4 装出 4。容量 7 试 dp[3]+4=6，没有原来的 7 大，不更新，保持 7。
放石头 1：放最后一块石头 1：把零碎缝补上。dp[3]=2+1=3（就是 {2,1}）、dp[5]=4+1=5、dp[1]=1。容量 7 试 dp[6]+1=7，和原值并列，仍是 7。
取最大一堆：四块石头都放完了。看容量上限 dp[7]=7：在「不超过半和 7」的前提下，一堆最多能凑到 7（就是 {2,4,1}）。
算答案：一堆是 7，另一堆 14−7=7，两堆差 = 0。换算公式：剩重 = total − 2×dp[7] = 14 − 14 = 0。这就是最后剩下的最小重量。
以后看到「把数组分两堆、让两堆差最小」，一律转成背包：在 sum÷2 的容量里求最大子集和，差就是 sum − 2×它。和目标和、分割等和子集是同一个套路。
参考代码（Python）
1total = sum(stones)
2target = total // 2 # 半容量
3dp = [0] * (target + 1) # dp[j]=容量 j 内最大子集和
4for x in stones:
5 for j in range(target, x - 1, -1): # 0-1: 从大到小，到 x 为止
6 dp[j] = max(dp[j], dp[j - x] + x) # 这块石头 不选 / 选
7return total - 2 * dp[target] # 总和 减 两倍最大一堆复杂度分析
- 时间复杂度：O(n × sum) —— n 块石头，每块扫一遍约 sum÷2 个容量格
- 空间复杂度：O(sum) —— 只用一行 dp 数组，长度是半和
套路模板
记住骨架：容量取半和、0-1 背包求最大子集和、答案 = 总和 − 2×它。凡是「让两部分尽量接近」的题都套它。
1target = sum(a) // 2 # 容量取半和
2dp = [0] * (target + 1) # 求最大子集和：初值 0
3for x in a:
4 for j in range(target, x - 1, -1): # 0-1 背包，必须从大到小
5 dp[j] = max(dp[j], dp[j - x] + x)
6return sum(a) - 2 * dp[target] # 答案 = 总和 − 2×最大一堆易错点
- 错误写法：直接把 dp[target] 当答案返回 → 正确写法：dp[target] 是最大一堆，答案要 total − 2×dp[target]（dp 求的是「最接近半和的子集和」，不是最终剩重；两堆差 = 总和减两倍这一堆）
- 错误写法：内层从小到大 → 正确写法：0-1 背包内层从大到小（从小到大会让同一块石头被装进同一堆两次，变成完全背包就错了）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。