1049. 最后一块石头的重量 II
思路：
因为含有两个石头的相撞，所以需要把dp的目标值改成sum/2，
然后取得这个目标值的最大值，然后对sum-2*target
代码：
1 // 要求：有多个石头，两两撞击，取得剩下的石头的最小值 2 // ——》一定要碰到最后一个 3 // 注意： 4 // 1，x==y: 两个粉碎，x<y: y = y-x 5 // 2，可能剩下一个或者0个 那么怎么判断是0还是1？ 6 // 7 // 背包问题： 8 // dp[n]：当有N个物品的时候，当前重量的最小值 9 // 10 // 11 // 怎么设置？ 已经直到重量是这些，但是终止条件是什么？ 12 // 13 // 物品：石头 价值：大小，重量 个数 14 // 容量：物品的数量 15 // 16 // dp[n]: 撞的话需要取两个石头，但是当前遍历的只有一个石头 17 // 1,不撞 dp[n] 18 // 2，撞： dp[n] = dp[n+1] - (2x)[第一个是遍历y，使得x属于<=y] 19 // 20 21 // 22 // 如果涉及两个东西之间的比较，可以往容量为sum/2那里思考 23 // dp[n]: 当容量为N 时候的最大值 24 // 25 int lastStoneWeightII(vector<int>& stones) { 26 if (stones.size() == 1) return stones[0]; 27 28 int sum_ = 0; 29 for (int num : stones) 30 { 31 sum_ += num; 32 } 33 34 vector<int> dp((sum_ / 2)+1, 0); 35 36 for (int i = 0; i < stones.size(); i++) 37 { 38 for (int j = (sum_ / 2); j >= stones[i]; j--) 39 { 40 dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]); 41 } 42 } 43 44 int result = sum_ - 2 * dp[sum_ / 2]; 45 if (result < 0) return 0; 46 else return result; 47 }