最后一块石头的重量II

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (int x : stones) sum += x;
        vector<int> dp(sum + 1, 0);
        for (int i = 0; i < stones.size(); i++) {
            for (int j = sum / 2; j >= stones[i]; j--)
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
        }
        return sum - 2 * dp[sum / 2];
    }
};