【Day43】1049. 最后一块石头的重量 II

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

    题解:

class Solution {
public:
    int lastStoneWeightII(vector& stones) {
        auto sum = accumulate(stones.begin(), stones.end(), 0);
        vector dp(sum / 2 + 1);
        for (const auto& stone : stones) {
            for (auto j = sum / 2; j >= stone; j--) {
                dp[j] = max(dp[j], dp[j - stone] + stone);
            }
        }
        return sum - dp[sum / 2] * 2;
    }
};

   转载规则


《【Day43】1049. 最后一块石头的重量 II》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day44】879. 盈利计划 【Day44】879. 盈利计划
879. 盈利计划集团里有 n 名员工,他们可以完成各种各样的工作创造利润。 第 i 种工作会产生 profit[i] 的利润,它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作,就不能参与另一项工作。 工作的任何至少产生
2021-06-09
下一篇 
【Day42】494. 目标和 【Day42】494. 目标和
494. 目标和给你一个整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ,然后串联起所有整数,可以构造一个 表达式 : 例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在
2021-06-07
  目录