LeetCode 1049. 最后一块石头的重量 II
题目描述
题意分析
每次任选两块石头相撞：重量相同则一起消失，不同则留下两者重量差的一块。不断操作到至多一块石头，求能够实现的最小剩余重量，没有剩余时返回零。
每次选哪两块由我们决定，不能固定选择当前最重的两块。石头即使重量相同也仍是不同的可选对象，每一块原石只能参与一次分组归属，不能重复使用它的重量。
解法：0/1 背包接近半和
核心思路
[!blue]
相撞本质上做减法。把最终残块反向展开，每个原石重量都会带一个正号或负号，因此最终结果可写成两组原石总重之差的绝对值。这意味着任何碰撞结果，都不会小于所有分组中能得到的最小差。
还需要说明最优分组差确实能通过碰撞实现。先按最优分组给石头分两边，只拿不同边的残块相撞；较重一边保留差值残块，相等则一起消失。每次操作都保持两边的总重差，且每个残块都代表一组原石的带符号差。
最终某一边为空。若另一边仍有多块正重量残块，总重为最优差
D，取其中一块重量r，有0 < r < D。将这个残块代表的全部原石正负号反转，会得到合法的新分组，差变为abs(D - 2r) < D，与原分组最优矛盾。因此最优分组最终只能留下至多一块，最小分组差与最小碰撞结果相等。设总重量为
S，较轻组重量为x <= S / 2，两组差就是S - 2x。要让差最小，应找不超过一半的最大可达子集和，而不是只判断能否恰好平分。令
dp[cap]表示从已经处理的石头中选若干块、总重不超过cap时能达到的最大重量。处理石头stone时，可以不选，保留旧值；也可以选，得到dp[cap - stone] + stone，两者取最大。每块石头只能使用一次，所以容量从大到小更新。读取较小容量
cap - stone时，它还属于处理当前石头之前的状态，保证不会重复选同一块。全部处理后返回S - 2 * dp[S / 2]。
解题步骤
- 计算总重
sum，令背包容量target = sum / 2。- 创建全零数组
dp，表示只选空集时各容量下可达重量均为零。- 逐块处理石头，容量从
target倒序到当前重量。- 更新
dp[cap] = max(dp[cap], dp[cap - stone] + stone)。- 用总重减去两倍最佳半组重量，返回最小差。
代码实现
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int stone : stones) {
sum += stone;
}
int target = sum / 2;
// 每个容量记录不超过它的最大可达重量，未必恰好装满
int[] dp = new int[target + 1];
for (int stone : stones) {
// 容量倒序保证每块石头只选一次
for (int cap = target; cap >= stone; cap--) {
dp[cap] = Math.max(dp[cap], dp[cap - stone] + stone);
}
}
// 另一组重量是总和减所选组，最终取两组差
return sum - 2 * dp[target];
}
}
func lastStoneWeightII(stones []int) int {
sum := 0
for _, stone := range stones {
sum += stone
}
target := sum / 2
// 每个容量记录不超过它的最大可达重量，未必恰好装满
dp := make([]int, target+1)
for _, stone := range stones {
// 容量倒序保证每块石头只选一次
for cap := target; cap >= stone; cap-- {
candidate := dp[cap-stone] + stone
if candidate > dp[cap] {
dp[cap] = candidate
}
}
}
// 另一组重量是总和减所选组，最终取两组差
return sum - 2*dp[target]
}
复杂度分析
- 时间复杂度：$O(n(T+1))$，其中 $n$ 为石头数量，$T=\lfloor S/2\rfloor$ 为背包容量，每块石头至多扫描整段容量。
- 空间复杂度：$O(T+1)$，只保存一行容量状态。
关键点总结
[!green]
- 将碰撞顺序问题转成正负分组，最优分组差可以由跨组碰撞实现。
- 只找不超过半和的最大子集和，另一组自动由未选石头组成。
- 状态含义是“不超过容量时的最大可达重量”，不要求恰好装满。
- 倒序读取旧状态，将同一块石头的使用次数限制为一次。
易错点总结
[!yellow]
- 正序更新会读取本轮刚更新的较小容量，等价于允许重复使用同一块石头。
- 将容量向上取整后仍用
S - 2x，可能选到超过半和的组而得到负结果。- 只计算
S - x得到的是另一组重量，还需要再减去所选组重量。- 总重为奇数并不表示无解，它只意味着不可能完全抵消为零，仍应求最小正差。
- 只模拟每次撞最大的两块，限制了本题允许的选择，不能保证得到最优剩余重量。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 416. 分割等和子集 | 中等 | 通过给石头分配正负组转成子集和，本题找最接近总和一半的可达值，而非只判断恰好平分。 |
| 956. 最高的广告牌 | 困难 | 同样用两组差值建模，原题允许舍弃材料并最大化等高，本题全部石头参与并最小化剩余差。 |
| 494. 目标和 | 中等 | 用容量动态规划表示可达和或组合数；本题尽量把总重量划分得接近一半，该题将正负分配转为指定和子集计数。 |
| 474. 一和零 | 中等 | 用容量动态规划表示可达和或组合数；本题尽量把总重量划分得接近一半，该题把容量扩展为零和一的两维预算。 |