最后一块石头 II 图解题解

这道题到底在问什么

输入

stones=[2,4,1,5,3]

输出

1

最优解：一步一步想明白

1. 3于是变成 0-1 背包：dp[i][w]=用前 i 块、容量 w 内能凑到的最大重量。下面一张二维表逐格填。
2. 4第 0 行：一块石头都还没加入，不管容量多大都只能凑出 0。这是递推的起点。
3. 5加入石头 2，容量 0 比 2 还小，放不进，只能照搬上方 dp[0][0]=0。
4. 6照搬上方，填入 0。
5. 7加入石头 2，容量 1 比 2 还小，放不进，只能照搬上方 dp[0][1]=0。
6. 8照搬上方，填入 0。
7. 9加入石头 2，容量 2：不选它=上方 0；选它=腾出 2 后的 dp[0][0]=0 再加 2 = 2。
8. 10选这块更划算，填入 2。
9. 11加入石头 2，容量 3：不选它=上方 0；选它=腾出 2 后的 dp[0][1]=0 再加 2 = 2。
10. 12选这块更划算，填入 2。
11. 13加入石头 2，容量 4：不选它=上方 0；选它=腾出 2 后的 dp[0][2]=0 再加 2 = 2。
12. 14选这块更划算，填入 2。
13. 15加入石头 2，容量 5：不选它=上方 0；选它=腾出 2 后的 dp[0][3]=0 再加 2 = 2。
14. 16选这块更划算，填入 2。
15. 17加入石头 2，容量 6：不选它=上方 0；选它=腾出 2 后的 dp[0][4]=0 再加 2 = 2。
16. 18选这块更划算，填入 2。
17. 19加入石头 2，容量 7：不选它=上方 0；选它=腾出 2 后的 dp[0][5]=0 再加 2 = 2。
18. 20选这块更划算，填入 2。
19. 21加入石头 4，容量 0 比 4 还小，放不进，只能照搬上方 dp[1][0]=0。
20. 22照搬上方，填入 0。
21. 23加入石头 4，容量 1 比 4 还小，放不进，只能照搬上方 dp[1][1]=0。
22. 24照搬上方，填入 0。
23. 25加入石头 4，容量 2 比 4 还小，放不进，只能照搬上方 dp[1][2]=2。
24. 26照搬上方，填入 2。
25. 27加入石头 4，容量 3 比 4 还小，放不进，只能照搬上方 dp[1][3]=2。
26. 28照搬上方，填入 2。
27. 29加入石头 4，容量 4：不选它=上方 2；选它=腾出 4 后的 dp[1][0]=0 再加 4 = 4。
28. 30选这块更划算，填入 4。
29. 31加入石头 4，容量 5：不选它=上方 2；选它=腾出 4 后的 dp[1][1]=0 再加 4 = 4。
30. 32选这块更划算，填入 4。
31. 33加入石头 4，容量 6：不选它=上方 2；选它=腾出 4 后的 dp[1][2]=2 再加 4 = 6。
32. 34选这块更划算，填入 6。
33. 35加入石头 4，容量 7：不选它=上方 2；选它=腾出 4 后的 dp[1][3]=2 再加 4 = 6。
34. 36选这块更划算，填入 6。
35. 37加入石头 1，容量 0 比 1 还小，放不进，只能照搬上方 dp[2][0]=0。
36. 38照搬上方，填入 0。
37. 39加入石头 1，容量 1：不选它=上方 0；选它=腾出 1 后的 dp[2][0]=0 再加 1 = 1。
38. 40选这块更划算，填入 1。
39. 41加入石头 1，容量 2：不选它=上方 2；选它=腾出 1 后的 dp[2][1]=0 再加 1 = 1。
40. 42不选更划算（或相等），填入 2。
41. 43加入石头 1，容量 3：不选它=上方 2；选它=腾出 1 后的 dp[2][2]=2 再加 1 = 3。
42. 44选这块更划算，填入 3。
43. 45加入石头 1，容量 4：不选它=上方 4；选它=腾出 1 后的 dp[2][3]=2 再加 1 = 3。
44. 46不选更划算（或相等），填入 4。
45. 47加入石头 1，容量 5：不选它=上方 4；选它=腾出 1 后的 dp[2][4]=4 再加 1 = 5。
46. 48选这块更划算，填入 5。
47. 49加入石头 1，容量 6：不选它=上方 6；选它=腾出 1 后的 dp[2][5]=4 再加 1 = 5。
48. 50不选更划算（或相等），填入 6。
49. 51加入石头 1，容量 7：不选它=上方 6；选它=腾出 1 后的 dp[2][6]=6 再加 1 = 7。
50. 52选这块更划算，填入 7。
51. 53加入石头 5，容量 0 比 5 还小，放不进，只能照搬上方 dp[3][0]=0。
52. 54照搬上方，填入 0。
53. 55加入石头 5，容量 1 比 5 还小，放不进，只能照搬上方 dp[3][1]=1。
54. 56照搬上方，填入 1。
55. 57加入石头 5，容量 2 比 5 还小，放不进，只能照搬上方 dp[3][2]=2。
56. 58照搬上方，填入 2。
57. 59加入石头 5，容量 3 比 5 还小，放不进，只能照搬上方 dp[3][3]=3。
58. 60照搬上方，填入 3。
59. 61加入石头 5，容量 4 比 5 还小，放不进，只能照搬上方 dp[3][4]=4。
60. 62照搬上方，填入 4。
61. 63加入石头 5，容量 5：不选它=上方 5；选它=腾出 5 后的 dp[3][0]=0 再加 5 = 5。
62. 64不选更划算（或相等），填入 5。
63. 65加入石头 5，容量 6：不选它=上方 6；选它=腾出 5 后的 dp[3][1]=1 再加 5 = 6。
64. 66不选更划算（或相等），填入 6。
65. 67加入石头 5，容量 7：不选它=上方 7；选它=腾出 5 后的 dp[3][2]=2 再加 5 = 7。
66. 68不选更划算（或相等），填入 7。
67. 69加入石头 3，容量 0 比 3 还小，放不进，只能照搬上方 dp[4][0]=0。
68. 70照搬上方，填入 0。
69. 71加入石头 3，容量 1 比 3 还小，放不进，只能照搬上方 dp[4][1]=1。
70. 72照搬上方，填入 1。
71. 73加入石头 3，容量 2 比 3 还小，放不进，只能照搬上方 dp[4][2]=2。
72. 74照搬上方，填入 2。
73. 75加入石头 3，容量 3：不选它=上方 3；选它=腾出 3 后的 dp[4][0]=0 再加 3 = 3。
74. 76不选更划算（或相等），填入 3。
75. 77加入石头 3，容量 4：不选它=上方 4；选它=腾出 3 后的 dp[4][1]=1 再加 3 = 4。
76. 78不选更划算（或相等），填入 4。
77. 79加入石头 3，容量 5：不选它=上方 5；选它=腾出 3 后的 dp[4][2]=2 再加 3 = 5。
78. 80不选更划算（或相等），填入 5。
79. 81加入石头 3，容量 6：不选它=上方 6；选它=腾出 3 后的 dp[4][3]=3 再加 3 = 6。
80. 82不选更划算（或相等），填入 6。
81. 83加入石头 3，容量 7：不选它=上方 7；选它=腾出 3 后的 dp[4][4]=4 再加 3 = 7。
82. 84不选更划算（或相等），填入 7。
83. 85看最右下角 dp[5][7]=7：这堆最接近一半。差 = 15−2×7 = 1，就是最后剩下的最小重量。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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]

int lastStoneWeightII(vector<int>& stones){
    int s = 0; for(int x : stones) s += x;
    int t = s / 2;
    vector<int> dp(t + 1, 0);
    for(int x : stones)
        for(int w = t; w >= x; --w)
            dp[w] = max(dp[w], dp[w - x] + x);
    return s - 2 * dp[t];
}

int lastStoneWeightII(int[] stones){
    int s = 0; for(int x : stones) s += x;
    int t = s / 2;
    int[] dp = new int[t + 1];
    for(int x : stones)
        for(int w = t; w >= x; w--)
            dp[w] = Math.max(dp[w], dp[w - x] + x);
    return s - 2 * dp[t];
}

复杂度

面试官可能追问