dp背包问题——1049.最后一块石头的重量II

本题其实就是尽量让石头分成重量相同的两堆&＃xff0c;相撞之后剩下的石头最小&＃xff0c;这样就化解成01背包问题了。

和416. 分割等和子集非常像&＃xff0c;只需要使用石头总重量的一半作为背包容量&＃xff0c;通过01背包的dp算法&＃xff0c;计算出一半容量所能装入的最大石头重量&＃xff0c;就能使得最后剩余的石头最小

本题物品的重量为stones[i]&＃xff0c;物品的价值也为stones[i]

先写出常见的二维数组解法&＃xff1a;

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {if(stones.size() &＃61;&＃61; 1){return stones[0];}int n &＃61; stones.size();int sum &＃61; accumulate(stones.begin(), stones.end(), 0);int content &＃61; sum / 2;vector<vector<int>> dp(n, vector<int>(content &＃43; 1, 0)); // 由于j是容量&＃xff0c;不仅是下标&＃xff0c;还有实际意义&＃xff0c;需要content&＃43;1for(int j &＃61; 1; j <&＃61; content; j&＃43;&＃43;){dp[0][j] &＃61; j >&＃61; stones[0] ? stones[0] : 0;}// 先遍历物品&＃xff0c;再遍历容量for(int i &＃61; 1; i < n; i&＃43;&＃43;){for(int j &＃61; 1; j <&＃61; content; j&＃43;&＃43;){if(j < stones[i]){// 当前背包容量 <物品重量dp[i][j] &＃61; dp[i-1][j];}else{dp[i][j] &＃61; max(dp[i-1][j], dp[i-1][j-stones[i]] &＃43; stones[i]);}}}return sum - 2 * dp[n-1][content];}
};


通过滚动数组优化&＃xff0c;尤其需要注意&＃xff1a;

1. 为什么需要从后往前遍历容量
2. 为什么遍历容量时&＃xff0c;没有显式判断当前容量j小于当前物品重量nums[i]

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {if(stones.size() &＃61;&＃61; 1){return stones[0];}int n &＃61; stones.size();int sum &＃61; accumulate(stones.begin(), stones.end(), 0);int content &＃61; sum / 2;// vector> dp(n, vector(content &＃43; 1, 0)); // 由于j是容量&＃xff0c;不仅是下标&＃xff0c;还有实际意义&＃xff0c;需要content&＃43;1vector<int> dp(content &＃43; 1, 0);// 用第一个物品初始化dp数组for(int j &＃61; 1; j <&＃61; content; j&＃43;&＃43;){dp[j] &＃61; j >&＃61; stones[0] ? stones[0] : 0;}// 先遍历物品&＃xff0c;再遍历容量for(int i &＃61; 1; i < n; i&＃43;&＃43;){// 滚动数组&＃xff0c;从后往前遍历容量for(int j &＃61; content; j >&＃61; stones[i]; j--){dp[j] &＃61; max(dp[j], dp[j-stones[i]] &＃43; stones[i]);}}return sum - 2 * dp[content];}
};