题目
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 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
解题
方法一：动态规划
让一堆石头，分为尽可能相近的两堆，那么两堆的差就是剩下的最小的石头重量。
所以我们可以把它看成背包问题，容量为target=sum/2, 让它装尽可能多的石头，作为一堆，剩下的作为另一堆，这样两者的差才会最小。
dp[target]里是容量为target的背包所能背的最大重量。
那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。
在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。
class Solution { public: int lastStoneWeightII(vector<int>& stones) { int sum=accumulate(stones.begin(),stones.end(),0); int target=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[j]=max(dp[j],dp[j-stones[i]]+stones[i]); } } return sum-dp[target]-dp[target]; } };
java
class Solution { public int lastStoneWeightII(int[] stones) { int sum=0; for(int stone:stones) sum+=stone; int target=sum/2; int[] dp=new int[target+1]; for(int i=0;i<stones.length;i++){ for(int j=target;j>=stones[i];j--){ dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]); } } return sum-dp[target]*2; } }
