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

?代码随想录

class Solution {

    public int lastStoneWeightII(int[] stones) {
        int sum = 0;

        for(int i : stones){
            sum += i;
        }

        int target = sum >> 1;

        int [] dp = new int[target+1];

        for(int i = 0 ; i < stones.length; i ++){

            for(int j = target ; j >= stones[i] ; j -- ){
                dp[j] = Math.max(
                    dp[j],
                    dp[j-stones[i]] + stones[i]
                );
            }
        }
        return sum - 2* dp[target];
 
    }
}