本文共 2317 字，大约阅读时间需要 7 分钟。

1. 题目

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

示例：输入：[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]，这就是最优值。 提示：1 <= stones.length <= 301 <= stones[i] <= 1000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/last-stone-weight-ii

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

• 题目说任意两块石头可以相撞，转化为把n个石头分为2堆，任意一堆越接近总重s的一半
• 这两堆做差肯定就是最小的
• 那么就变成 0-1 背包，每个石头取或不取，求不超过s/2 的最大的重量

class Solution {
   	//C++public:    int lastStoneWeightII(vector
   
    & stones) {
       	int i, j, n = stones.size(), sum = accumulate(stones.begin(),stones.end(), 0);    	vector
    
     
      > dp(n+1,vector
      
       (sum/2+1, false));    	dp[0][0] = true;//dp[i][w], 遍历完第i个石头，可以得到重量为w吗？    	for(i = 1; i <= n; i++)//样本维度    	{
       		for(j = 0; j <= sum/2; ++j)//重量维度    		{
       			if(dp[i-1][j])    			{
       				dp[i][j] = dp[i-1][j];//不取    				if(j+stones[i-1] <= sum/2)//不超，取    					dp[i][j+stones[i-1]] = true;    			}    		}    	}    	j = sum/2;    	while(dp[n][j] != true)//最接近一半的重量是 j     		j--;    	return sum-2*j;//一半是sum-j，一半是 j,做差    }};
      
     
    
   

• 状态只跟上一行有关，再用逆序滚动数组，节省存储空间

class Solution {
   	//C++public:    int lastStoneWeightII(vector
   
    & stones) {
       	int i, j, n = stones.size(), sum = accumulate(stones.begin(),stones.end(), 0);    	vector
    
      dp(sum/2+1, false);    	dp[0] = true;//dp[w], 遍历完第i个石头，可以得到的重量为w吗？    	for(i = 1; i <= n; i++)//样本维度    	{
       		for(j = sum/2; j >= 0; --j)//重量维度    		{
       			if(dp[j] && j+stones[i-1] <= sum/2)    				dp[j+stones[i-1]] = true;    		}    	}    	j = sum/2;    	while(dp[j] != true)    		j--;    	return sum-2*j;    }};
    
   

8 ms 8.2 MB

python3 解答

class Solution:# py3    def lastStoneWeightII(self, stones: List[int]) -> int:        n = len(stones)        s = sum(stones)        dp = [False]*(s//2+1)        dp[0] = True        for i in range(1,n+1):            for j in range(s//2,-1,-1):                if dp[j] and j+stones[i-1] <= s//2:                    dp[j+stones[i-1]] = True        j = s//2        while not dp[j]:            j -= 1        return s-2*j

52 ms 13.6 MB

转载地址：https://michael.blog.csdn.net/article/details/106980126 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！