leetcode 1049. Last Stone Weight II
题意:与第一题不同，这次是挑任意两块相撞，求最终剩下的最小值。
思路：可以看成将当前数组分成两个堆，两堆里面的石头分别对撞。也就是求两个堆的石头后，然后做差，求最小。可以用dp来做。dp[i]表示能否组成重量为i的堆，那么另外一个堆就是sum-i。当i与sum/2最接近时，两个差最小。
代码：
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;vector<int> dp(1600, 0);dp[0]=1;for (auto stone : stones){sum += stone;for (int i = 1500; i - stone >= 0; i--)if (dp[i - stone])dp[i] = 1;}for (int i = sum/2 ; i >= 0; i--)if (dp[i])return (sum - i) - i;return 0;}
};