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

01背包

import java.util.Arrays;

class Solution {
    public int lastStoneWeightII(int[] stones) {

        /**
         * 题意可以理解为，将石头尽可能分成相等的两份，最后差值就是最小剩余重量
         * 剩下的部分和《416. 分割等和子集》一样
         * dp[j]定义为总重量为j的背包中，能放入的最大石头重量，最大值为target
         */
        int sum = Arrays.stream(stones).sum();
        int target = sum / 2;

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

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

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

        return sum - 2 * dp[target];
    }
}

/**
 * 时间复杂度 O(n^2)
 * 空间复杂度 O(n)
 */

https://leetcode-cn.com/problems/last-stone-weight-ii/