最后一块石头 II 图解题解

这道题到底在问什么

stones

[2, 7, 4, 1]

总和 / 半容量

14 / 7

输出

0

先想最直接的笨办法

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

最优解：一步一步想明白

1. 3最直接的想法：每块石头要么进左堆、要么进右堆，n 块就有 2ⁿ 种分法，逐一算两堆差再取最小。石头一多就算爆了，重复枚举太浪费。
2. 4设其中一堆和为 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。
3. 5容量 0~7 的最大子集和表头是容量 0 到 7。dp[j] 表示「容量 j 内能装出的最大子集和」，全部先初始成 0（什么都不装，和为 0）。下面一块块石头往里塞。
4. 6dp[2..7]=2放石头 2，内层从大到小扫容量：只要容量不小于 2，就能装下它，dp[j]=dp[j−2]+2=2。容量 2 到 7 全变成 2。容量 1 装不下，保持 0。
5. 7dp[7]=7放石头 7：只有容量正好 7 才装得下它。dp[7]=max(原来的 2, dp[0]+7)=7。现在容量 7 能装出和 7（就单独那块 7）。
6. 8dp[6..2] 不变注意负例：容量 6（以及更小）想装石头 7，j−7 会变成负数，根本装不下。这些格子只能沿用「不选这块石头」的旧值，dp[6] 还是 2。这就是循环只扫到 x 为止的原因。
7. 9dp[4..7] 更新放石头 4：容量 6 现在能装 {2,4}=6（dp[2]+4）；容量 5、4 装出 4。容量 7 试 dp[3]+4=6，没有原来的 7 大，不更新，保持 7。
8. 10dp 填满放最后一块石头 1：把零碎缝补上。dp[3]=2+1=3（就是 {2,1}）、dp[5]=4+1=5、dp[1]=1。容量 7 试 dp[6]+1=7，和原值并列，仍是 7。
9. 11dp[7]=7四块石头都放完了。看容量上限 dp[7]=7：在「不超过半和 7」的前提下，一堆最多能凑到 7（就是 {2,4,1}）。
10. 1214 − 2×7 = 0一堆是 7，另一堆 14−7=7，两堆差 = 0。换算公式：剩重 = total − 2×dp[7] = 14 − 14 = 0。这就是最后剩下的最小重量。
11. 15以后看到「把数组分两堆、让两堆差最小」，一律转成背包：在 sum÷2 的容量里求最大子集和，差就是 sum − 2×它。和目标和、分割等和子集是同一个套路。

⚠️ 容易写错的地方

完整代码（Python）

class Solution:
    def lastStoneWeightII(self, stones):
        total = sum(stones)
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for w in stones:
            for s in range(target, w - 1, -1):
                dp[s] = dp[s] or dp[s - w]
        for s in range(target, -1, -1):
            if dp[s]:
                return total - 2 * s

target = sum(a) // 2                     # 容量取半和
dp = [0] * (target + 1)                  # 求最大子集和：初值 0
for x in a:
    for j in range(target, x - 1, -1):   # 0-1 背包，必须从大到小
        dp[j] = max(dp[j], dp[j - x] + x)
return sum(a) - 2 * dp[target]          # 答案 = 总和 − 2×最大一堆

复杂度

面试官可能追问