LeetCode 1049. 最后一块石头的重量 II
1049. 最后一块石头的重量 II - 力扣（LeetCode）
有一堆石头，用整数数组 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
【思路】尽量把这些石头分成重量总和近似相等的两堆。分成数值近似相等的两个集合，也就是这里边的两堆石头。尽量凑成，凑不成也没关系。凑不成的话那两堆石头相撞的话，所剩的重量它也一定是最小的。那此时这就是一个背包问题，每一个物品只能用一次，所以说这就是一个0-1背包。
本题和 LeetCode 416.分割等和子集几乎就是一样的， 唯一的区别就是在最后判断的时候，是有一点出入的。
- 在0-1背包中的dp[j]
dp[j] 背包容量j 最大价值dp[j]
最大重量dp[j]
dp[j] = max(dp[j],dp[j-weight[i]] + value[j]);
由于在本题中，价值和重量相等，
dp[j] = max(dp[j],dp[j-stones[i]] + stones[i]);
- 可以求出一堆石头的重量，也就是 dp[target];
- 也就可以求出另一堆石头的重量，也就是 sum - dp[target]
- 然后这两堆石头进行碰撞：(sum - dp[target]) - dp[target]
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;for(int i=0;i<stones.size();i++) {sum += stones[i];}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];}
};// stones = [2,7,4,1,8,1]
// 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y// 2 7 4 1 8 1// 思路：尽量分成重量差不多的两堆,然后再进行相减
// 思考:那如何分成这样的两堆呢？// 1.dp[j]
// dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石头的重量和// 2.确定target
// 2 + 7 + 4 + 1 + 8 + 1 = 23
// target = sum / 2 = 23/2 = 11;
// {2,7,1,1} {4,8}
// 11 - 10 = 1// ① dp[target];
// ② sum - dp[target]
// ③ (sum - dp[target]) - dp[target] // 3.动态递归方程
// dp[j] = max(dp[j],dp[j-stones[i]] + stones[i]);// 4.初始化dp
// dp[0] = 0
// 一维数组dp初始化为0
// vector<int> dp(target+1,0);// 5.遍历
// 先遍历物品，再从后往前遍历背包// 价值 重量
// 物品0 2 2
// 物品1 7 7
// 物品2 4 4
// 物品3 1 1
// 物品4 8 8
// 物品5 1 1// 0 1 2 3 4 5 6 7 8 9 10 11 背包重量j
// | | | | | | | | | | | |
// 0 0 0 0 0 0 0 0 0 0 0 0 初始化dp
// 0 0 2 2 2 2 2 2 2 2 2 2 (可挑选物品0)->产生最大价值
// 0 0 2 2 2 2 2 7 7 9 9 9 (可挑选物品0、物品1)->产生最大价值
// 0 0 2 2 4 4 6 7 7 9 9 11 (可挑选物品0、物品1、物品2)->产生最大价值
// 0 1 2 3 4 5 6 7 8 9 10 11 (可挑选物品0、物品1、物品2、物品3)->产生最大价值
// 0 1 2 3 4 5 6 7 8 9 10 11 (可挑选物品0、物品1、物品2、物品3、物品4)->产生最大价值
// 0 1 2 3 4 5 6 7 8 9 10 11 (可挑选物品0、物品1、物品2、物品3、物品4、物品5)->产生最大价值来自代码随想录的课堂截图
>>往期文章：
解决0-1背包问题（方案一）:二维dp数组_呵呵哒(￣▽￣)"的博客-CSDN博客
解决0-1背包问题（方案二）：一维dp数组（滚动数组）_呵呵哒(￣▽￣)"的博客-CSDN博客