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

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

思路

为了得到最后一块石头的最小可能重量，我们可以将问题转为子集和的问题。找到一个子集，使得元素之和与剩余元素之后的差最小。也就是说，我们希望把石头分成两个集合，使得两个子集的重量差最小。由于我们可以通过将一个子集的重量从总重量中减去来得到另一个子集的重量，因此，我们的目标可以简化为寻找一个子集，其元素之和最接近总重量的一半。这样，两个子集之间的重量差就会是最小的。

解题方法

我们使用动态规划解决这个问题。定义一个一维数组 dp，其中 dp[j] 表示是否能够通过选择一些石头（不超过 j）达到总和 j。我们初始化 dp[0] 为 true，因为总和为 0 是总是可以实现的。
遍历数组 nums 中的每个元素 num，对于每一个 num，我们更新 dp 数组，使得 dp[j] 变为 dp[j-num]+num 和 dp[j] 中较大的值，只要 j >= num。
最后，dp 数组中的最大值就是我们要求的子集的近似最大重量。

复杂度

时间复杂度:

$O(n\cdot m)$，其中 n 是数组 nums 的长度，m 是 nums 中所有元素的和除以 2 的结果。

空间复杂度:

$O(m)$，其中 m 是 nums 中所有元素的和除以 2 的结果。这是因为我们需要一个大小为 m+1 的 dp 数组。

Code

class Solution {
    public int lastStoneWeightII(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 向下取整 01背包
        int near = near(nums, sum / 2);
        return sum - near - near;
    }
    public int near(int[] nums, int t) {
        int[] dp = new int[t + 1];
        for(int num : nums) {
            for(int j = t; j >= num; j--) {
                dp[j] = Math.max(dp[j], dp[j - num] + num);
            }
        }
        return dp[t];
    }
}