1049. 最后一块石头的重量 II
题目描述
输入整数数组 stones，stones[i] 是第 i 块石头的重量。
每一轮可以任选两块石头相撞，设重量为 x <= y。若 x == y，两块都消失；否则重 x 的消失，另一块重量变为 y - x。
持续进行，直到剩下的石头不超过一块。返回最后剩下那块石头可能的最小重量；若可以全部消失，返回 0。
示例 1
输入：stones = [2,7,4,1,8,1] 输出：1
解释：例如先撞 2 和 4、再撞 7 和 8、再撞 2 和 1、最后撞 1 和 1，剩下重 1 的石头。
示例 2
输入：stones = [31,26,33,21,40] 输出：5
数据范围
1 <= stones.length <= 301 <= stones[i] <= 100
解题思路
不管怎么撞，每块石头最后不是被加就是被减，结果等于“正号组之和 - 负号组之和”的绝对值，而且任意分组都能撞出来。设较小一组和为 c，结果为 total - 2c，所以要找不超过 total/2 的最大可凑出的和 c。这是 0-1 背包：dp[c] 表示能否选若干块石头恰好凑出 c；每块石头 s 从大到小更新 dp[c] |= dp[c - s]。
为什么正确
处理完前 k 块石头后，dp[c] 为真当且仅当可以从前 k 块中选一些（每块至多一次）凑出和 c。
复杂度分析
时间 O(n·S)，空间 O(S)，S = total/2。
易错点
内层循环必须从大到小，否则同一块石头会被用多次（变成完全背包）。不要用“每次撞最重的两块”的贪心，那是 1046 题的规则。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
total = sum(stones)
half = total // 2
dp = [False] * (half + 1)
dp[0] = True
for s in stones:
for c in range(half, s - 1, -1):
if dp[c - s]:
dp[c] = True
for c in range(half, -1, -1):
if dp[c]:
return total - 2 * c
return totalclass Solution {
public int lastStoneWeightII(int[] stones) {
int total = 0; for (int s : stones) total += s;
int half = total / 2;
boolean[] dp = new boolean[half + 1];
dp[0] = true;
for (int s : stones) {
for (int c = half; c >= s; c--) {
if (dp[c - s]) {
dp[c] = true;
}
}
}
for (int c = half; c >= 0; c--) {
if (dp[c]) {
return total - 2 * c;
}
}
return total;
}
}class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int total = 0; for (int s : stones) total += s;
int half = total / 2;
vector<bool> dp(half + 1, false);
dp[0] = true;
for (int s : stones) {
for (int c = half; c >= s; c--) {
if (dp[c - s]) {
dp[c] = true;
}
}
}
for (int c = half; c >= 0; c--) {
if (dp[c]) {
return total - 2 * c;
}
}
return total;
}
};func lastStoneWeightII(stones []int) int {
total := 0; for _, s := range stones { total += s }
half := total / 2
dp := make([]bool, half+1)
dp[0] = true
for _, s := range stones {
for c := half; c >= s; c-- {
if dp[c-s] {
dp[c] = true
}
}
}
for c := half; c >= 0; c-- {
if dp[c] {
return total - 2*c
}
}
return total
}var lastStoneWeightII = function(stones) {
const total = stones.reduce((a, b) => a + b, 0);
const half = Math.floor(total / 2);
const dp = new Array(half + 1).fill(false);
dp[0] = true;
for (const s of stones) {
for (let c = half; c >= s; c--) {
if (dp[c - s]) {
dp[c] = true;
}
}
}
for (let c = half; c >= 0; c--) {
if (dp[c]) {
return total - 2 * c;
}
}
return total;
};function lastStoneWeightII(stones: number[]): number {
const total = stones.reduce((a, b) => a + b, 0);
const half = Math.floor(total / 2);
const dp = new Array(half + 1).fill(false);
dp[0] = true;
for (const s of stones) {
for (let c = half; c >= s; c--) {
if (dp[c - s]) {
dp[c] = true;
}
}
}
for (let c = half; c >= 0; c--) {
if (dp[c]) {
return total - 2 * c;
}
}
return total;
}