最后一块石头的重量 II

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