最后一块石头的重量 II

/*
 * 思路：
 * 1. 将所有石头总重量的一半作为背包容量。
 * 2. 使用动态规划找到最接近这个容量的组合。
 * 3. 最小可能重量是总重量减去两倍的最大可达背包重量。
 */
import java.util.Arrays;

public class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int target = sum / 2;
        int[] dp = new int[target + 1];
        Arrays.stream(stones).forEach(stone -> {
            for (int j = target; j >= stone; j--) {
                dp[j] = Math.max(dp[j], dp[j - stone] + stone);
            }
        });
        return sum - 2 * dp[target];
    }
}