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

本文主要是介绍leetcode 1049.最后一块石头的重量II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：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];}
};

这篇关于leetcode 1049.最后一块石头的重量II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---