Description Link to heading

1049.last-stone-weight-ii

Solution Link to heading

In reality, it’s still a 01-pack-problem.

What it want to get is when you divide the array into two part with least difference of their sum, what the difference is. If you are aware of this, just write code similar to 416.partition-equal-subset-sum.

Code Link to heading 

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