思路：01背包

其實這道題我們可以轉化一下，乍一看有點像區間dp，很像區間合并那種類型。

但是，后來發現，這道題的精髓在于你如何轉成背包問題。我們可以把這個石頭分成兩堆，然后求出來這兩堆的最小差值就行了，得到的就是我們的最后的剩余石頭。

比較靈活，有點很難想的感覺，這才是背包問題的難點，如何轉化是挺重要的一點。

那么，就先把總和求出來，然后分成兩堆，對于總和的一半作為容量，價值就是石頭的重量。

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