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]);

1. 可以求出一堆石头的重量，也就是 dp[target];
2. 也就可以求出另一堆石头的重量，也就是 sum - dp[target]
3. 然后这两堆石头进行碰撞：(sum - dp[target]) - dp[target]  

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(int i=0;isize();i++) {
            sum += stones[i];
        }
        int target = sum / 2;
        vector<int> dp(target+1,0);
        for(int i=0;isize();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 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博客