有一堆石头，用整数数组 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
解题思路
这题乍一看好像有点复杂，但是我们可以知道的是，我们必须要做变化，才能进行状态表示，因为此时状态很难表示出来，所以要做题目的转变！
题意转换
我们以这个数组 [a, b, c, d, e] 为例，因为用字母来表示，等会看起来效果会比数字更加直观！
此时我们就假设我们的方案就是最优解，每一步如下所示：
- 此时 b 和 d 碰撞，且 b > d，则碰撞后得到
[a, b - d, c, e] - 此时 a 和 c 碰撞，且 a < c，则碰撞后得到
[b - d, c - a, e] - 此时 b - d 和 e 碰撞，且 b - d < e，则碰撞后得到
[c - a, e - b + d] - 此时让剩下的两个石头碰撞，且前者小于后者，得到
[e - b + d - c + a]
看到这里，是不是觉得有点熟悉，是不是就转变成我们前面做的 494. 目标和 这道题啦！只不过我们不是去求目标和的次数，而是要去求加减表达式的最小结果！
此时我们还得再转化一次，因为如果不再转换一次的话，就得考虑正负号的问题，此时的思路和目标和那道题其实差不多，但是细节有差别！
如下图所示，我们可以把数组中的值这么划分：
此时根据我们的需求，也就是求表达式的最小结果，那么不就是求 a - b 的最小值吗！而我们又能知道 a + b = sum，而我们是可以求出 sum 的也就是数组元素的和，此时就转化为了一个小学时候就出现过的问题了：给定一个数，问我们将其如何拆分可以获得差值最小的两个数，那不就又转化为了 a - b 了吗，对不对！
我们可以很明显的得到这两个数是越接近总和的一半的时候，它们的差值越小， 而我们知道总和是 sum，那不就是将 sum 分为两半吗，此时得到的两个数的差值就是最小的！而我们只需要求其中的 a 即可，也就是达到一半即可！
总结一下，问题最后转变为：在数组中选择一些数字，这些数字要尽量的接近数字元素总和的一半 sum / 2！此时我们把数组元素看作物品，其值就是物品的价值和体积，问题就变成了 01背包 问题！
状态表示
根据 “题目要求 + 经验“，定义状态表示为 dp[i][j] 表示在前 i 个元素中选择，总和不超过 j 即不超过当前背包空间，此时所有元素的「最大和」。
状态转移方程
状态转移方程和之前基本是一模一样的，对于当前的 dp 值，无非就是两种状态：选和不选。
初始化
开辟虚拟行列，然后全部初始化为 0 即可！
因为只用到上一行的数据，所以考虑第一行初始化即可！第一行表示不选物品，此时最大价值肯定为 0。
而第一列则跟着状态转移方程去填表完成即可！
遍历顺序
从上往下，从左往右遍历即可！
返回值
和之前不太一样，这道题要求的是所有元素的最大和，但是我们前面题目转换的时候讲过，我们只需要达到数组元素和一半即 dp[n][sum / 2]。
还没结束，题目要求的是最小的结果，根据我们的转换过程，我们只算出来了 a 也就是 dp[n][sum / 2]，而 b 就等于 sum - a 即 sum - [n][sum / 2]，此时我们要求 a - b，那么就是 2 * dp[n][sum / 2] - sum。
但是注意可能会出现负数，所以要返回 2 * dp[n][sum / 2] - sum 的绝对值！
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
// 先计算出数组元素和
int sum = 0;
for(auto e : stones)
sum += e;
// 创建dp表，开辟虚拟行列
int m = stones.size();
int n = sum / 2;
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 从上往下，从左往右遍历
for(int i = 1; i <= m; ++i)
{
for(int j = 0; j <= n; ++j)
{
dp[i][j] = dp[i - 1][j];
// 注意与原数组的下标映射关系
if(j >= stones[i - 1])
dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
}
}
// 返回值
int a = dp[m][n];
int b = sum - dp[m][n];
return abs(a - b);
}
};优化
所有的「背包问题」，都可以进行空间上的优化。
对于 01背包 类型的，我们的优化策略是：
- 删掉第一维
- 修改第二层循环的遍历顺序即可
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
// 先计算出数组元素和
int sum = 0;
for(auto e : stones)
sum += e;
// 创建dp表，开辟虚拟行列
int m = stones.size();
int n = sum / 2;
vector<int> dp(n + 1, 0);
// 从上往下，从左往右遍历
for(int i = 1; i <= m; ++i)
{
for(int j = n; j >= stones[i - 1]; --j)
{
// 注意与原数组的下标映射关系
dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
}
}
// 返回值
int a = dp[n];
int b = sum - dp[n];
return abs(a - b);
}
};