一、题目内容 中等

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例1：

输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例2：

输入：stones = [31,26,33,21,40] 输出：5

示例3：

输入：stones = [1,2] 输出：1

提示：

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

    二、解题思路

    当给我们一个 stones 数组时，我们将其一分为二，看成两个整体，尽量分成两个等重的数组。
    将这两个整体看成 x、y，按照题目规则进行相消，结果就是最小。

    为什么可以看成两个整体呢？ 本质是，A、B 两组集合中的元素相消。7. 最后一块石头的重量 II(1049) - 图1 因为7. 最后一块石头的重量 II(1049) - 图2 所以分拆成小元素相减的结果，肯定也等于整体相减的结果，不必纠结。

那么问题就化归为，怎么将 stones 尽可能分成等重的数组，这跟 6. 分割等和子集（416）思路如出一辙。

确定了如下四点，才能把01背包问题套到本题上来。

  • 背包的体积为 sum / 2，取整数
  • 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
  • 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
  • 背包中每一个元素是不可重复放入。

以上分析完，我们就可以套用 01 背包，来解决这个问题了。

动规五部曲分析如下：

  1. 确定dp数组以及下标的含义

01背包中，dp[j] 表示： 容量为 j 的背包，所背的物品价值可以最大为 dp[j]。
套到本题，dp[j] 表示 背包总容量是 j，最大可以凑成 j 的子集总和为 dp[j]。

jmax = sum / 2

  1. 确定递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
本题，相当于背包里放入石头，那么石头 i 的重量是 nums[i]，其价值也是 nums[i]。
所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

  1. dp 数组如何初始化

在 01 背包，一维 dp 如何初始化，已经讲过，从 dp[j] 的定义来看，首先 dp[0] 一定是 0。
如果题目给的价值都是正整数，那么非 0 下标都初始化为 0 就可以了。
如果题目给的价值有负数，那么非 0 下标就要初始化为负无穷。
这样才能让 dp 数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

  1. 确定遍历顺序

如果使用一维 dp 数组，物品遍历的 for 循环放在外层，遍历背包的 for 循环放在内层，且内层 for 循环倒序遍历！

  1. for (let i = 0; i < nums.length; i++) {
  2.   for (let j = mid; j >= nums[i]; j--) {
  3.     dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])
  4.   }
  5. }

  1. 举例推导 dp 数组

    三、具体代码

    1. /**
    2. * @param {number[]} stones
    3. * @return {number}
    4. */
    5. var lastStoneWeightII = function (stones) {
    6. const sum = stones.reduce((pre, cur) => pre + cur, 0)
    7. const mid = Math.floor(sum / 2)
    8. const dp = new Array(mid + 1).fill(0)
    9. // 遍历物品
    10. for (let i = 0; i < stones.length; i++) {
    11.  // 遍历背包
    12.  for (let j = mid; j >= stones[i]; j--) {
    13.    dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])
    14.  }
    15. }
    17. return sum - 2 * dp[mid]
    18. };

    四、其他解法