---

dp专题8 1049. 最后一块石头的重量 II

原创 于 2024-01-03 15:12:40 发布 · 粉丝可见 · 500 阅读 · 8 · 11 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/135363991

本题链接： 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目：

思路：

由题意，石头的相撞，求最后相撞后剩余的最后一个石头最小的重量是多少。

看到题目的这里，都往取哪些石头的方式去想了，我们不如换个思路，将这堆石头分成两堆，其中一堆尽可能的石头之和，为总石头之和的一半那边靠，然后将这两堆石头相撞，剩余的就一定是重量最小的石头了。

所以归根结底，还是背包问题，将 总石头之和的一半作为背包容量，另一堆重量 为 sum - dp[sum / 2];   最后相减即可。

代码详解如下：

inline int lastStoneWeightII(vector<int>& stones) 
{
	vector<int>dp(3000,0);	// 定义 dp 数组
	
	int sum = 0;	// 获取石头总重量
	for(int &i:stones) sum += i;
	
	// 获取另一堆重量目标
	int v = sum / 2;
	
	// 开始 dp 过程，取该石头和不取该石头的尽可能最大重量
	for(int &i:stones)
	{
		for(int j = v;j >= i;--j)
		{
			dp[j] = max(dp[j],dp[j - i] + i);
		}
	}
	
	int a = dp[v];	// 一堆石头总重量
	int b = sum - dp[v];	// 另一对的石头总重量
	
	return abs(a - b);	// 返回最后剩余石头的最小重量
}

最后提交：