天天看点

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

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

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

        for(int i = 0;i < stones.length;i++){
            sum += stones[i];
        }
        int target = sum / 2;
        int[][] dp = new int[stones.length + 1][target + 1];

        for(int i = 1; i <= stones.length;i++){
            int x = stones[i - 1];
            for(int j = 0; j <= target;j++){
                dp[i][j] = dp[i - 1][j];
                if(j >= x) dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - x] + x);
            }
        }

        int res = sum - 2*dp[stones.length][target];
        return res;

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

        for(int i = 0;i < stones.length;i++){
            sum += stones[i];
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];

        for(int i = 1; i <= stones.length;i++){
            int x = stones[i - 1];
            for(int j = target; j >= x;j--){
                dp[j] = Math.max(dp[j],dp[j - x] + x);
            }
        }

        int res = sum - 2*dp[target];
        return res;

    }
}
           

思路还是可以转变为0-1背包问题,重量一半的情况下,能装下的最大值,使左右两边的石头尽量均衡,这样可以达到碰撞后重量最小。