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

2024-01-03 16:35:04

本题链接:力扣(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);	// 返回最后剩余石头的最小重量
}

最后提交:

文章来源:https://blog.csdn.net/hacker_51/article/details/135363991
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。