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

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

最后提交：