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 }
标签：stones,return,int,1049,随想录,石头,II,sum,dp From： https://www.cnblogs.com/smartisn/p/17564878.html