最后一块石头的重量-ii

Tips

题目类型: Dynamic Programming

背包问题汇总

题目

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

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

• 如果 x == y, 那么两块石头都会被完全粉碎；
• 如果 x != y, 那么重量为 x 的石头将会完全粉碎, 而重量为 y 的石头新重量为 y-x.

最后, 最多只会剩下一块石头. 返回此石头最小的可能重量. 如果没有石头剩下, 就返回 0.

提示:

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

示例

输入: 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], 这就是最优值.

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

题解

比起 1046. 最后一块石头的重量, 这道题变成了任意取两块石头, 因此就没法排序了. 因此可以这样思考: 如果想要最小的可能重量, 其实可以抽象成两堆, 两堆相撞接近 0 就好, 那么此时问题就是有一堆石头, 每个石头都有自己的重量, 如何装满或是尽可能接近最大重量为 sum / 2 的背包.

从解法上和 0-1 背包的原生题一模一样, 要注意求 capacity 是向下取整; dp[n][capacity] 代表每堆最接近 capacity 的数, 所以最终结果是 sum - dp[n][capacity] * 2

二维数组

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeightII = function (stones) {
  const n = stones.length
  if (n === 1) return stones[0]

  const sum = stones.reduce((acc, val) => acc + val)
  const capacity = Math.floor(sum / 2)

  const dp = new Array(n + 1).fill(0).map(() => new Array(capacity + 1).fill(0))
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      if (w - stones[i - 1] < 0) {
        dp[i][w] = dp[i - 1][w]
      } else {
        dp[i][w] = Math.max(
          dp[i - 1][w],
          dp[i - 1][w - stones[i - 1]] + stones[i - 1],
        )
      }
    }
  }

  return sum - dp[n][capacity] * 2
}

一维数组

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeightII = function (stones) {
  const n = stones.length
  if (n === 1) return stones[0]

  const sum = stones.reduce((acc, val) => acc + val)
  const capacity = Math.floor(sum / 2)

  const dp = new Array(capacity + 1).fill(0)
  for (let i = 0; i < n; i++) {
    for (let w = capacity; w >= stones[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - stones[i]] + stones[i])
    }
  }

  return sum - dp[capacity] * 2
}