1049.Last-Stone-Weight-II

1049. Last Stone Weight II

题目地址

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

题目描述

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are destroyed, and
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

Example 1:
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

Example 2:
Input: stones = [31,26,33,21,40]
Output: 5

Example 3:
Input: stones = [1,2]
Output: 1

Constraints:
1 <= stones.length <= 30
1 <= stones[i] <= 100

代码

Approach #1

这道题，相当于用加号和减号把石头的重量连起来，并使结果最小。所以问题转换为把石头分为两拨，一拨是带加号，一拨是带减号。目标是求带减号的那拨石头，使其和<=sum/2,并接近于sum/2，这就相当于选石头放进背包，使背包尽可能的满，背包的容量为sum/2，各个石头的体积和质量相等都为stones[i]。

Time: O(1) && Space: O(1)

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += stones[i];
        }

        int target = sum / 2;
        int[] dp = new int[target + 1];

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

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