题目
有一堆石头，用整数数组 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提示：
1 <= stones.length <= 301 <= stones[i] <= 100
解答
- 动态规划
这是一道动态规划问题。我们可以定义一个 dp 数组，其中 dp[i] 表示背包容量为 i 时能够得到的最大价值。这里价值就是石头的重量。
具体来说，对于每一块石头，我们可以选择将其放入背包中，也可以不放入背包中。如果我们选择将其放入背包中，则可以得到的最大价值为 dp[j-stones[i]]+stones[i]，其中 j-stones[i] 表示剩余背包容量，dp[j-stones[i]] 表示剩余背包容量为 j-stones[i] 时能够得到的最大价值，stones[i] 表示当前石头的重量。
遍历完所有的石头后，dp[target] 就是能够得到的最大价值，其中 target 是所有石头重量之和的一半（因为我们要得到最终得到的石头的最小可能重量，因此需要将原问题转化为求解容量为 sum/2 的背包能够得到的最大价值）。
最终得到的石头的重量就是 sum - 2*dp[target]，其中 sum 是所有石头的重量之和。
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = accumulate(stones.begin(), stones.end(), 0); // 计算所有石头重量之和
int target = sum / 2; // 将原问题转化为求解容量为 sum/2 的背包能够得到的最大价值
vector<int> dp(target+1, 0); // 定义动态规划数组
for(int i=0; i<stones.size(); i++) { // 遍历每一块石头
for(int j=target; j>=stones[i]; j--) { // 从后往前更新 dp 数组
dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]); // 更新 dp 数组
}
}
return sum - 2*dp[target]; // 返回最终得到的石头的重量
}
};在上面的代码中，我们首先使用std::accumulate库函数对石头的重量进行求和，得到所有石头的总重量sum。接着，我们将原问题转化为求解容量为sum/2的背包能够得到的最大价值，因此定义了一个target变量来保存这个值。
然后，我们定义了一个长度为target+1的dp数组，其中dp[i]表示背包容量为i时能够得到的最大价值。这个数组的初始化值都是0。
接下来，我们遍历每一块石头，并对每一块石头进行背包问题的动态规划更新。具体来说，对于第i块石头，我们从target向stones[i]遍历，更新所有dp[j]（j>=stones[i]）。更新公式为dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
这里dp[j-stones[i]]表示在放入第i块石头前剩余的背包容量，因此需要从dp[j-stones[i]]中加上当前石头的重量stones[i]才能得到在放入第i块石头后的最大价值。最后，我们返回最终得到的石头的重量，即sum-2*dp[target]。