From
Leetcode
Status
AC
Date
Apr 2, 2024
Tags
动态规划
01背包
Difficulty
中等
题面
有一堆石头，用整数数组
stones 表示。其中 stones[i] 表示第 i 块石头的重量。每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为
x 和 y，且 x <= y。那么粉碎的可能结果如下：- 如果
x == y，那么两块石头都会被完全粉碎；
- 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回
0。示例 1：
示例 2：
思路
416. 分割等和子集 (opens new window)相当于是求背包是否正好装满，而本题是求背包最多能装多少。