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背包問題，重量一半的情況下，能裝下的最大值，使左右兩邊的石頭盡量均衡，這樣可以達到碰撞後重量最小。