leetcode_1049. Last Stone Weight II

1049. Last Stone Weight II

https://leetcode.com/problems/last-stone-weight-ii/

题意：从一堆石头里任选两个石头s1,s2，若s1==s2,则两个石头都被销毁，否则加入s1<s2，剩下一块重量为s2-s1的石头。重复上面的操作，直至只剩一块石头，或没有石头。问最后剩下的石头的重量最小为多少(0表示没有剩余石头)。

解法：

每次选两块石头进行相减问最后一块石头重量最小为多少，可以看作是将所有石头分为两波，使两波石头的差值的绝对值最小。

使用背包(snapsack)解决。dp[i]表示stones是否能组成重量为i的group。

class Solution

{

public:

    int lastStoneWeightII(vector<int>& stones)

    {

        int sum = accumulate(stones.begin(),stones.end(),);

        vector<bool> dp(sum/,);

        dp[]=;

        for(int s:stones)

            for(int j=sum/;j>=s;j--)

                dp[j] = dp[j]|dp[j-s];

        int res = sum;

        for(int i=;i<=sum/;i++)

            res = min(res, sum-dp[i]*i*);

        return res;

    }

};

巴特西

leetcode_1049. Last Stone Weight II_[DP]

最新文章

热门文章