# 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)

```java
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];
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/dynamic-programming/1049.last-stone-weight-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.