🌑1049.最后一块石头的重量II

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

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

如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

思路

基本思想

两个石头进行粉碎，重量越相近，粉碎得到的结果越小，所以可以应用 416题 的思想，将石头的重量求和，然后对半分作为背包的容量，求背包最大能装下多少，之后剩下的就是抵消不了的

背包最终装下的石头就是一个分组，剩下的石头是另外的分组，两组互相抵消剩下的值就是最终的结果，计算两相抵消剩下结果的公式为： $$ sum - dp[target] - dp[target] $$ 其中sum是所有石头的重量，target是背包的容量

执行流程

1. 计算背包的容量
2. 初始化dp数组
3. 求背包最大的价值（01背包的流程）
4. 求剩下的石头重量（套公式1）

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=accumulate(stones.begin(),stones.end(),0);
        int target=sum/2;
        vector<int> dp(target+1,0);
        for(int i=0;i<stones.size();++i){
            for(int j=target;j>=stones[i];--j){//装的下才有意义
                dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        //计算抵消剩下的部分
        return sum-dp[target]-dp[target];
    }   
};

总结

主要是将问题如何转化成01背包，一旦转化成01背包问题，一切迎刃而解

石头相互抵消应该选尽可能接近的才能留下更小的结果