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

题目链接

class Solution {
public:
    int lastStoneWeightII(vector& stones) {
        // 使用01背包解决，分两堆石头，装一半的石头，让两边的石头重量尽可能的接近
        // 最后背包装下的就是一半可以抵消的质量
        vector dp(1501, 0);
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) {
            sum += stones[i];
        }
        int target = sum / 2;

        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];
    }
};