# \[1049]\[困难]\[动态规划]\[背包] 最后一块石头的重量 II

## 题目描述

[1049. 最后一块石头的重量 II](https://leetcode-cn.com/problems/last-stone-weight-ii/)

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

示例：

```
输入：[2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
```

提示：

* 1 <= stones.length <= 30
* 1 <= stones\[i] <= 1000

## 解题思路

[LeetCode 1049 背包动态规划](https://www.cnblogs.com/19990219073x/p/10989013.html)

题目也可以转化成: 有一堆石头, 分成两堆, 如何分才能使两堆石头之间的重量差距最小. 每一堆石头都进行融合, 得到两块大石头, 然后他们之间的差值就是剩下石头的大小.

因此问题变成了一个01背包的问题, 将`n`块石头装进所有石头大小之和一半的背包中. 每块石头装入的奖励就是它本身的大小, 看最终在总大小一半的背包中, 能装满到什么程度, 这就是两堆中总大小较小的那一堆对应的最大值.

```python
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        half, n = total // 2, len(stones)
        dp = [[0] * (half + 1) for _ in range(n + 1)]

        for i in range(1, n + 1):
            stone = stones[i - 1]
            for j in range(1, half + 1):
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stone] + stone) if j >= stone else dp[i - 1][j]
        return abs(total - dp[-1][-1] * 2)
```

**滚动数组**版本, 需要从后向前遍历.

```python
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        half, n = total // 2, len(stones)
        dp = [0] * (half + 1)

        for i in range(n):
            stone = stones[i]
            for j in range(half, stone - 1, -1):
                dp[j] = max(dp[j], dp[j - stone] + stone)
        return abs(total - dp[-1] * 2)
```


---

# 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://blessbingo.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/1049-zui-hou-yi-kuai-shi-tou-de-zhong-liang-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.