1049.last-stone-weight-ii 最后一块石头的重量

问题描述

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

解题思路

实际上还是一个01背包问题。本质上是在求将数组分成差值最小的两部分之后，这两部分的差值，理解了这一点之后，参照416.分割等和子集写代码就好了。

代码

#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];
    }
};