signed

QiShunwang

“诚信为本、客户至上”

力扣每日一题:1049. 最后一块石头的重量 II

2021/6/9 0:03:14   来源:

目录

  • 题目:1049. 最后一块石头的重量 II
    • 示例1
    • 示例2
    • 示例3
    • 提示:
  • 解题思路
  • 解题代码
    • (1)动态规划
    • (2)动态规划+空间优化

题目:1049. 最后一块石头的重量 II

难度: 中等

题目
有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0。

示例1

输入:stones = [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],这就是最优值。

示例2

输入:stones = [31,26,33,21,40]
输出:5

示例3

输入:stones = [1,2]
输出:1

提示:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

`

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/last-stone-weight-ii/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。



解题思路

  该题需要转化为背包问题求解。记石头的总重量为sum,符号为负值的石头重量之和为neg,剩余符号为正的石头重量之和为sum-neg,所以最后所剩石头=sum - neg - neg = sum - 2 * neg。要使得最好一个石头尽可能地小,那么neg要尽可能的大,无线接近[sum / 2],而这就是背包问题的容量。 所以本题变为背包容量为[sum / 2],物品重量和价值均为stones[i]的0-1背包问题。

解题代码

(1)动态规划

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int n = stones.size(), m = sum / 2;
        //dp[i + 1][j]表示前i块石头能否构成重量为j的元素
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        dp[0][0] = true;
        for (int i = 0; i < n ; i++)
        {
            for (int j = 0; j <= m; j++)
            {
                if (j < stones[i])
                {
                    dp[i + 1][j] = dp[i][j];
                }
                else
                {
                    dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]];
                }
            }
        }
        for (int j = m;; j--)
        {
            if (dp[n][j])
            {
                return sum - 2 * j;
            }
        }
    }
};

(2)动态规划+空间优化

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int n = stones.size(), m = sum / 2;
        vector<int> dp(m + 1);
        dp[0] = 1;
        for (auto num : stones)
        {
            for (int j = m; j >= num; j--)
            {
                dp[j] |= dp[j - num];
            }
        }
        for (int j = m;; j--)
        {
            if (dp[j])
            {
                return sum - 2 * j;
            }
        }
        


    }
};