题目描述
思路解析动画文字版
于是变成 0-1 背包：dp[i][w]=用前 i 块、容量 w 内能凑到的最大重量。下面一张二维表逐格填。
第 0 行：一块石头都还没加入，不管容量多大都只能凑出 0。这是递推的起点。
加入石头 2，容量 0 比 2 还小，放不进，只能照搬上方 dp[0][0]=0。
照搬上方，填入 0。
加入石头 2，容量 1 比 2 还小，放不进，只能照搬上方 dp[0][1]=0。
照搬上方，填入 0。
加入石头 2，容量 2：不选它=上方 0；选它=腾出 2 后的 dp[0][0]=0 再加 2 = 2。
选这块更划算，填入 2。
加入石头 2，容量 3：不选它=上方 0；选它=腾出 2 后的 dp[0][1]=0 再加 2 = 2。
选这块更划算，填入 2。
加入石头 2，容量 4：不选它=上方 0；选它=腾出 2 后的 dp[0][2]=0 再加 2 = 2。
选这块更划算，填入 2。
加入石头 2，容量 5：不选它=上方 0；选它=腾出 2 后的 dp[0][3]=0 再加 2 = 2。
选这块更划算，填入 2。
加入石头 2，容量 6：不选它=上方 0；选它=腾出 2 后的 dp[0][4]=0 再加 2 = 2。
选这块更划算，填入 2。
加入石头 2，容量 7：不选它=上方 0；选它=腾出 2 后的 dp[0][5]=0 再加 2 = 2。
选这块更划算，填入 2。
加入石头 4，容量 0 比 4 还小，放不进，只能照搬上方 dp[1][0]=0。
照搬上方，填入 0。
加入石头 4，容量 1 比 4 还小，放不进，只能照搬上方 dp[1][1]=0。
照搬上方，填入 0。
加入石头 4，容量 2 比 4 还小，放不进，只能照搬上方 dp[1][2]=2。
照搬上方，填入 2。
加入石头 4，容量 3 比 4 还小，放不进，只能照搬上方 dp[1][3]=2。
照搬上方，填入 2。
加入石头 4，容量 4：不选它=上方 2；选它=腾出 4 后的 dp[1][0]=0 再加 4 = 4。
选这块更划算，填入 4。
加入石头 4，容量 5：不选它=上方 2；选它=腾出 4 后的 dp[1][1]=0 再加 4 = 4。
选这块更划算，填入 4。
加入石头 4，容量 6：不选它=上方 2；选它=腾出 4 后的 dp[1][2]=2 再加 4 = 6。
选这块更划算，填入 6。
加入石头 4，容量 7：不选它=上方 2；选它=腾出 4 后的 dp[1][3]=2 再加 4 = 6。
选这块更划算，填入 6。
加入石头 1，容量 0 比 1 还小，放不进，只能照搬上方 dp[2][0]=0。
照搬上方，填入 0。
加入石头 1，容量 1：不选它=上方 0；选它=腾出 1 后的 dp[2][0]=0 再加 1 = 1。
选这块更划算，填入 1。
加入石头 1，容量 2：不选它=上方 2；选它=腾出 1 后的 dp[2][1]=0 再加 1 = 1。
不选更划算（或相等），填入 2。
加入石头 1，容量 3：不选它=上方 2；选它=腾出 1 后的 dp[2][2]=2 再加 1 = 3。
选这块更划算，填入 3。
加入石头 1，容量 4：不选它=上方 4；选它=腾出 1 后的 dp[2][3]=2 再加 1 = 3。
不选更划算（或相等），填入 4。
加入石头 1，容量 5：不选它=上方 4；选它=腾出 1 后的 dp[2][4]=4 再加 1 = 5。
选这块更划算，填入 5。
加入石头 1，容量 6：不选它=上方 6；选它=腾出 1 后的 dp[2][5]=4 再加 1 = 5。
不选更划算（或相等），填入 6。
加入石头 1，容量 7：不选它=上方 6；选它=腾出 1 后的 dp[2][6]=6 再加 1 = 7。
选这块更划算，填入 7。
加入石头 5，容量 0 比 5 还小，放不进，只能照搬上方 dp[3][0]=0。
照搬上方，填入 0。
加入石头 5，容量 1 比 5 还小，放不进，只能照搬上方 dp[3][1]=1。
照搬上方，填入 1。
加入石头 5，容量 2 比 5 还小，放不进，只能照搬上方 dp[3][2]=2。
照搬上方，填入 2。
加入石头 5，容量 3 比 5 还小，放不进，只能照搬上方 dp[3][3]=3。
照搬上方，填入 3。
加入石头 5，容量 4 比 5 还小，放不进，只能照搬上方 dp[3][4]=4。
照搬上方，填入 4。
加入石头 5，容量 5：不选它=上方 5；选它=腾出 5 后的 dp[3][0]=0 再加 5 = 5。
不选更划算（或相等），填入 5。
加入石头 5，容量 6：不选它=上方 6；选它=腾出 5 后的 dp[3][1]=1 再加 5 = 6。
不选更划算（或相等），填入 6。
加入石头 5，容量 7：不选它=上方 7；选它=腾出 5 后的 dp[3][2]=2 再加 5 = 7。
不选更划算（或相等），填入 7。
加入石头 3，容量 0 比 3 还小，放不进，只能照搬上方 dp[4][0]=0。
照搬上方，填入 0。
加入石头 3，容量 1 比 3 还小，放不进，只能照搬上方 dp[4][1]=1。
照搬上方，填入 1。
加入石头 3，容量 2 比 3 还小，放不进，只能照搬上方 dp[4][2]=2。
照搬上方，填入 2。
加入石头 3，容量 3：不选它=上方 3；选它=腾出 3 后的 dp[4][0]=0 再加 3 = 3。
不选更划算（或相等），填入 3。
加入石头 3，容量 4：不选它=上方 4；选它=腾出 3 后的 dp[4][1]=1 再加 3 = 4。
不选更划算（或相等），填入 4。
加入石头 3，容量 5：不选它=上方 5；选它=腾出 3 后的 dp[4][2]=2 再加 3 = 5。
不选更划算（或相等），填入 5。
加入石头 3，容量 6：不选它=上方 6；选它=腾出 3 后的 dp[4][3]=3 再加 3 = 6。
不选更划算（或相等），填入 6。
加入石头 3，容量 7：不选它=上方 7；选它=腾出 3 后的 dp[4][4]=4 再加 3 = 7。
不选更划算（或相等），填入 7。
看最右下角 dp[5][7]=7：这堆最接近一半。差 = 15−2×7 = 1，就是最后剩下的最小重量。
几个边界自己心算一遍。
两个高频追问。
参考代码
def lastStoneWeightII(stones): s = sum(stones); t = s // 2 dp = [0] * (t + 1) for x in stones: for w in range(t, x - 1, -1): dp[w] = max(dp[w], dp[w - x] + x) return s - 2 * dp[t]复杂度
- 时间：O(n·sum)，n 块石头 × 容量 sum/2
- 空间：O(sum)，一维滚动数组
易错点
面试追问把动画讲成自己的话
追问它和「分割等和子集」(LC416) 什么关系？
追问为什么相撞问题能等价成分两堆？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题