南宁seo 网站收录,学校网站建,医药网站建设公司,深圳感染人数最新消息1049. 最后一块石头的重量 II
有一堆石头#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合#xff0c;从中选出任意两块石头#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y#xff0c;且 x y。那么粉碎的可能结果…1049. 最后一块石头的重量 II
有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x lt; y。那么粉碎的可能结果如下
如果 x y那么两块石头都会被完全粉碎如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。
最后**最多只会剩下一块 **石头。返回此石头 **最小的可能重量 **。如果没有石头剩下就返回 0。
示例 1
**输入**stones [2,7,4,1,8,1]
**输出**1
**解释**
组合 2 和 4得到 2所以数组转化为 [2,7,1,8,1]
组合 7 和 8得到 1所以数组转化为 [2,1,1,1]
组合 2 和 1得到 1所以数组转化为 [1,1,1]
组合 1 和 1得到 0所以数组转化为 [1]这就是最优值。示例 2
**输入**stones [31,26,33,21,40]
**输出**5提示
1 lt; stones.length lt; 301 lt; stones[i] lt; 100 这一题很难想到背包问题 这道题看出是背包问题比较有难度 最后一块石头的重量从一堆石头中,每次拿两块重量分别为x,y的石头,若xy,则两块石头均粉碎;若xy,两块石头变为一块重量为y-x的石头求最后剩下石头的最小重量(若没有剩下返回0) 问题转化为把一堆石头分成两堆,求两堆石头重量差最小值
class Solution {
public:int lastStoneWeightII(vectorint stones) {int n stones.size();int sum 0;for (auto u : stones) {sum u;}int bag sum / 2;vectorint dp(bag 1, 0);for (int i 0; i n; i) {for (int j bag; j stones[i]; j--) {dp[j] max(dp[j], dp[j - stones[i]] stones[i]);}}return sum - dp[bag];}
};
