题目

image.png

思路

说实话，我是真想不到啊要怎么转化为0-1背包。。。
结果大神说，把石头分两堆对撞咯。。。。。。。。。。。我靠。

  1. 假设想要得到最优解，我们需要按照如下顺序操作石子：[(sa, sb), (sc, sd), ... ,(si, sj), (sp, sq)][(sa,sb),(sc,sd),...,(si,sj),(sp,sq)]。
  3. 其中 abcdijpqabcdijpq 代表了石子编号，字母顺序不代表编号的大小关系。
  5. 如果不考虑「有放回」的操作的话，我们可以划分为两个石子堆（正号堆/负号堆）：
  7. 将每次操作中「重量较大」的石子放到「正号堆」，代表在这次操作中该石子重量在「最终运算结果」中应用 ++ 运算符
  8. 将每次操作中「重量较少/相等」的石子放到「负号堆」，代表在这次操作中该石子重量在「最终运算结果」中应用 -− 运算符
  9. 这意味我们最终得到的结果，可以为原来 stonesstones 数组中的数字添加 +/-+/− 符号，所形成的「计算表达式」所表示。
  11. 那有放回的石子重量如何考虑？
  13. 其实所谓的「有放回」操作，只是触发调整「某个原有石子」所在「哪个堆」中，并不会真正意义上的产生「新的石子重量」。
  15. 什么意思呢？
  17. 假设有起始石子 aa 和 bb，且两者重量关系为 a \geq ba≥b，那么首先会将 aa 放入「正号堆」，将 bb 放入「负号堆」。重放回操作可以看作产生一个新的重量为 a - ba−b 的“虚拟石子”，将来这个“虚拟石子”也会参与某次合并操作，也会被添加 +/-+/− 符号：
  19. 当对“虚拟石子”添加 ++ 符号，即可 +(a - b)+(a−b)，展开后为 a - ba−b，即起始石子 aa 和 bb 所在「石子堆」不变
  20. 当对“虚拟石子”添加 -− 符号，即可 -(a - b)−(a−b)，展开后为 b - ab−a，即起始石子 aa 和 bb 所在「石子堆」交换
  21. 因此所谓不断「合并」&「重放」，本质只是在构造一个折叠的计算表达式，最终都能展开扁平化为非折叠的计算表达式。
  23. 综上，即使是包含「有放回」操作，最终的结果仍然可以使用「为原来 stonesstones 数组中的数字添加 +/-+/− 符号，形成的“计算表达式”」所表示。

有了上述分析后，问题转换为：为 stonesstones 中的每个数字添加 +/-+/−，使得形成的「计算表达式」结果绝对值最小。
同时，由于想要「计算表达式」结果绝对值，因此我们需要将石子划分为差值最小的两个堆。
其实就是对「计算表达式」中带 -的数值提取公因数 -1−1，进一步转换为两堆石子相减总和，绝对值最小。
这就将问题彻底切换为 01 背包问题：从 stones数组中选择，凑成总和不超过 sum/2的最大价值。

var lastStoneWeightII = function(stones) {
    const sum =stones.reduce((x,y)=> x+y)
    const target =Math.floor(sum/2) //向下取整
    let dp =new Array(target+1).fill(0)

    for(let i=0;i<=stones.length;i++){
        for(let j=target;j>=stones[i];j--){
            dp[j] =Math.max(dp[j],dp[j-stones[i]]+stones[i])
        }
    }
    //分成两堆石头，sum-dp[target] 和 dp[target]
    return (sum-dp[target])-dp[target]

};