力扣 1049题 动态规划

推荐使用语雀阅读^[1]，因为有 LaTex 公式，其他方式排版不好。

最终还是回到了我的老本行^[2]，写题解。人生就像一场马拉松，跑得快很厉害，跑得远也很重要。

题目描述

解题思路

推荐阅读背包九讲^[3]，本题用到其中的第一部分，01 背包。因为每两块石头就能粉碎，可以试着把这些石头分为两份，分别为 a 份和 b 份，如果想要剩下的数字尽量小，那就要让 a 份和 b 份尽量相等，如果完全相等，那是最好的，这样答案就为 0，因为 a 份和 b 份总能全部抵消。那如果只看 a 份，就可以转换为：把这些石头放进一个容量为

的背包中，尽量放最多，这就让我们想到了什么，是 01 背包：

只不过在当前情景下

问题就转换为，有一个容量为

的背包，放入第 i 件物品的费用是

得到的价值还是

求价值最大，我们可以使用优化后的方式来编写代码：

时间复杂度是

代码如下：（本代码使用了 Lodash，因为力扣已经默认包含了这个库）

var lastStoneWeightII = function(stones) { const sSum = _.sum(stones); const n = stones.length; const volume = Math.floor(sSum / 2);
 const dp = Array(volume + 1).fill(0);
 for (let i = 0; i < n; i++) { const tmp = stones[i]; for (let j = volume; j >= tmp; j--) { dp[j] = Math.max(dp[j], dp[j - tmp] + tmp); } }
 return sSum - dp[volume] * 2;};

结语

最开始我也没有想到用一半的容量去跑 01 背包，看了别人的代码才知道，我一开始就想偏了，还是挺难的 😂

引用链接

[1] 语雀阅读: https://www.yuque.com/zcue/dev-blog/pyv79e
[2] 老本行: https://www.cnblogs.com/s1124yy/
[3] 背包九讲: https://github.com/tianyicui/pack
[4] GitHub: https://github.com/Acmu
[5] 掘金: https://juejin.im/user/5bcab884e51d450e81091745
[6] 语雀: https://www.yuque.com/zcue/dev-blog