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(),0); vector<bool> dp(sum/2,0); dp[0]=1; for(int s:stones) for(int j=sum/2;j>=s;j--) dp[j] = dp[j]|dp[j-s]; int res = sum; for(int i=0;i<=sum/2;i++) res = min(res, sum-dp[i]*i*2); return res; } };
转载于:https://www.cnblogs.com/jasonlixuetao/p/10890116.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/100908.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
