视频讲解：https://www.bilibili.com/video/BV14M411C7oV

https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html

1.本题还是和上一个分割等和子集的思路一样，不能被题意带着走，题目靠01背包问题，考虑要求最小的相撞的石头大小，考虑到将石头分成两堆数值接近的相减就是最小的大小，所以进行背包问题的解法。

CPP

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        if(stones.size() == 0)return 0;
        int sum = 0;
        for(int i = 0; i < stones.size(); i++){
            sum += stones[i];
        }
        int target = sum / 2;
        vector<int> dp(1501, 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 - 2*dp[target];
        
    }
};