【从0到1冲刺蓝桥杯国赛】每日一练——最后一块石头的重量Ⅱ
题目链接
力扣
https://leetcode-cn.com/problems/last-stone-weight-ii/
题目描述
题目分析
这道题目其实是01背包的一个变形，做过分割等和子集的话就很容易想到，解法几乎完全一样，就多了一个差值比较而已，大家可以看看下面这篇 【从0到1冲刺蓝桥杯国赛】每日一练——分割等和子集_战士小小白的博客-CSDN博客力扣https://leetcode-cn.com/problems/partition-equal-subset-sum/题目描述题目分析这道题其实用暴力也能做，回溯来实现，但是时间复杂度太高，AC不了；还是dp来做比较合适，这道题其实可以转化为01背包来做，背包的容量为所有数字和的一半，如果把背包装满了，那么返回true，否则false；在开始之前来个判断，如果数组所有元素之和是奇数，那么一定返回false；C++实现class Solution {publi...https://blog.csdn.net/weixin_53173524/article/details/124253817?spm=1001.2014.3001.5501
C++实现
class Solution {public: int lastStoneWeightII(vector& stones) { vector dp(1501,0); int sum = 0; for(int i = 0; i < stones.size(); i++) sum += stones[i]; int target = sum / 2; for(int i = 0; i = stones[i]; j--){ dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]); } } return sum - dp[target] - dp[target]; }};