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

二维数组

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int size = stones.length;
        if(size == 1) return stones[0];
        int sum= 0, target = 0;
        for(int i : stones ) {
            sum += i;
        }
        target = sum / 2;
        int [][] dp = new int [size][target + 1];
        for(int j = target; j >= stones[0]; j-- ) {
            dp[0][j] = stones[0];
        }
        for(int i = 1; i < size; i++ ) {
            for(int j = 0; j <= target; j++ ) {
                if(j < stones[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i] ] + stones[i]);
                }
            }
        }
        return sum - 2 * dp[size - 1][target];
    }
}

滚动数组

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int size = stones.length;
        if(size == 1) return stones[0];
        int sum = 0,target = 0;
        for(int i : stones ) {
            sum += i;
        }
        //向下取整（如 1 ，1/2 = 0）
        target = sum / 2;
        int dp[] = new int[sum + 1];
        for(int i = 0; i < size; 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];
    }
}