fyhub's blog

Appearance

1049.最后一块石头的重量-ii ​

思路 ​

本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成 01 背包问题了。

题解 ​

js
/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeightII = function (stones) {
  const dp = new Array(30 * 100).fill(0);
  const sum = stones.reduce((a, b) => a + b);
  // 最大的背包大小
  const target = Math.floor(sum / 2);
  // 遍历石头
  for (let i = 0; i < stones.length; i++) {
    // 倒序遍历背包容量
    for (let j = target; j >= stones[i]; j--) {
      // 背包容量j的最大重量 = max(不选石头i的最大重量, 选择石头i的最大重量 + 石头i的重量)
      dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
    }
  }
  // 剩下石头集合的重量 -  最大石头集合的重量
  return sum - dp[target] - dp[target];
};
/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeightII = function (stones) {
  const dp = new Array(30 * 100).fill(0);
  const sum = stones.reduce((a, b) => a + b);
  // 最大的背包大小
  const target = Math.floor(sum / 2);
  // 遍历石头
  for (let i = 0; i < stones.length; i++) {
    // 倒序遍历背包容量
    for (let j = target; j >= stones[i]; j--) {
      // 背包容量j的最大重量 = max(不选石头i的最大重量, 选择石头i的最大重量 + 石头i的重量)
      dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
    }
  }
  // 剩下石头集合的重量 -  最大石头集合的重量
  return sum - dp[target] - dp[target];
};