题目描述：

方法1：转化为背包问题，把石头尽可能分成两堆，求两堆石头重量差最小值，进一步转化为，将石头放进容量为sum/2的背包中，最大价值为MaxValue，最后(sum - MaxValue) - MaxValue即为题解

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(int i=0;i<stones.size();i++) sum += stones[i];
        //初始化dp数组
        vector<vector<int>>dp(stones.size(),vector<int>(sum/2+1,0));//背包容量为sum/2
        for(int j=sum/2;j>=stones[0];j--) dp[0][j] = stones[0];

        //更新dp数组
        for(int i=1;i<stones.size();i++){
            for(int j=1;j<=sum/2;j++){
                if(j - stones[i] > 0) dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);//放的下
                else dp[i][j] = dp[i-1][j];//放不下
            }
        }

        return sum - 2 * dp[stones.size()-1][sum/2];
    }
};

错误，无法通过所有样例

原因：更新dp数组时，j - stones[i] >= 0而不是 >0

方法2：变为1维dp数组

class Solution {
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];
    }
};