1049. 最后一块石头的重量 II #
- 标签:数组、动态规划
- 难度:中等
题目大意 #
有一堆石头,用整数数组 stones
表示,其中 stones[i]
表示第 i
块石头的重量。
每一回合,从石头中选出任意两块石头,将这两块石头一起粉碎。假设石头的重量分别为 x
和 y
。且 x ≤ y
,则结果如下:
- 如果
x == y
,则两块石头都会被完全粉碎; - 如果
x < y
,则重量为x
的石头被完全粉碎,而重量为y
的石头新重量为y - x
。
最后,最多只会剩下一块石头,返回此石头的最小可能重量。如果没有石头剩下,则返回 0。
解题思路 #
选取两块石头,重新放回去的重量是两块石头的差值绝对值。重新放回去的石头还会进行选取,然后进行粉碎,直到最后只剩一块或者不剩石头。
这个问题其实可以转化为:把一堆石头尽量平均的分成两对,求两堆石头重量差的最小值。
这就和「 0416. 分割等和子集」有点相似。两堆石头的重量要尽可能的接近数组总数量和的一半。
进一步可以变为:假设石头总重量和为 sum
,则问题为将一堆石头放进容量最多为 sum / 2
的背包中,获得的最大价值为 max_weight
(即其中一堆石子的重量),则另一堆石子的重量为 sum - max_weight
。则两者的差值为 sum - 2 * max_weight
,即为答案。
代码 #
|
|