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

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

## 解题思路
实际上还是一个[01背包问题](https://zwyyy456.vercel.app/zh/posts/tech/01-pack-problem/)。本质上是在求**将数组分成差值最小的两部分**之后，这两部分的差值，理解了这一点之后，参照[416.分割等和子集](https://zwyyy456.vercel.app/zh/posts/tech/416.partition-equal-subset-sum)写代码就好了。

## 代码
```cpp
#include <vector>
using std::vector;
class Solution {
  private:
    int max(int a, int b) {
        return a > b ? a : b;
    }

  public:
    int lastStoneWeightII(vector<int> &stones) {
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) {
            sum += stones[i];
        }
        vector<int> dp(sum / 2 + 1, 0);
        for (int i = 0; i < stones.size(); i++) {
            for (int j = sum / 2; j >= stones[i]; j--)
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
        }
        return sum - 2 * dp[sum / 2];
    }
};
```