动态规划
解题思路
难点：
- 尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就转化成 0-1 背包 问题了；
- 感觉和 leetcode🧑💻 416. 分割等和子集 非常像了；
- 本题物品的重量、物品的价值为 stones[i]；
- 对应着 0-1 背包 里的 物品重量 weight[i] 和 物品价值 value[i]；
- 最后 dp[sum/2] 里是容量为 sum/2 的背包所能背的最大重量，一堆石头的总重量是 dp[sum/2] ，另一堆就是 sum - dp[sum/2] ，那么最后相撞之后剩下的最小石头重量就是 sum - dp[sum/2] - dp[sum/2]；
确定 dp 数组以及下标的含义：dp[j] 表示容量（重量）为 j 的背包，最多可以容纳最大重量为 dp[j] 的重量；
确定递推公式：
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
- 01背包 的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])；
- 本题相当于背包里放入数值，那么物品 i 的重量、价值也是 stones[i] ，递推公式与 01背包 的递推公式一样；
如何初始化 dp 数组：
确定遍历顺序：
- 先遍历物品，再遍历背包；
- 状态值的更新只和它上边和左边的元素有关，把空间投影到一行后，状态转移（填表）的时候，从右边到左边更新状态值；
举例推导 dp 数组：
背包容量 j（j 最大为 sum/2） 0 1 2 3 4 5 6 7 8 9 10 11 最多可以容纳最大重量为 dp[j] 的重量 0 1 2 3 4 5 6 7 8 9 10 11
复杂度
-
时间复杂度：
O(mn)，m 是石头总重量的一半，n 为石头块数； -
空间复杂度：
O(m)；
代码实现
var lastStoneWeightII = function (stones) {
// 1. 对 stones 求和 sum
let sum = stones.reduce((s, n) => s + n);
// 2. 找到两队石头相近 sum/2，那么就找到了相撞之后剩下的最小石头重量
let bagSize = Math.floor(sum / 2);
// 3. 初始化 dp 滚动数组
let dp = new Array(bagSize + 1).fill(0);
// 4. 先遍历物品，再遍历背包容量
for (let i = 0; i < stones.length; ++i) { // 遍历物品
for (let j = bagSize; j >= stones[i]; --j) { // 遍历背包容量
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
// 5. 一堆石头的总重量是 dp[sum/2] ，另一堆就是 sum - dp[sum/2] ，那么最后相撞之后剩下的最小石头重量就是 sum - dp[sum/2] - dp[sum/2]
return sum - dp[bagSize] - dp[bagSize];
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 416. 分割等和子集
上一篇
评论
