1049. 最后一块石头的重量 II

题目地址：1049. 最后一块石头的重量 II - 力扣（LeetCode）

题解思路：01背包

时间复杂度：O(n*m)

空间复杂度：O(m)

代码:

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {// 01背包，容量和价值一样，即目标是最大化使用容量// 如[abcd]，抵消后可以为a+b+c-d，也可以是a+b-c-d，即一堆和-另一堆和的最小值// 第一堆 = sum - dp[sum/2]，第二堆 = dp[sum / 2]// 接下来开始dp，转化为找dp[]的最大值// dp[]: 容量为j的背包的最大值// 转移：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])// 初始化：dp[i] = 0// 顺序：先种类，后重量vector<int>dp(15001, 0);int sum = 0;for(auto i : stones) sum += i;int target = sum / 2;int size = stones.size();for(int i = 0; i < 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];}
};

416. 分割等和子集

题目地址：416. 分割等和子集 - 力扣（LeetCode）

题解思路：dp，01背包

时间复杂度：O(n^2)

空间复杂度：O(n)

代码:

class Solution {
public:bool canPartition(vector<int>& nums) {// 01背包，容量和价值一样，即目标是最大化使用容量// dp[]：容量为j的背包的最大价值// dp[i] = i，只要dp[sum / 2] = sum / 2就返回true// 初始化：dp[0] = 0// 顺序：种类，容量vector<int>dp(10001, 0);  // 200 * 100 / 2int sum = 0;for(auto i : nums) sum += i;int size = nums.size();for(int i = 0; i < size; i++){for(int j = sum / 2; j >= nums[i]; j--){dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}return dp[sum / 2] * 2 == sum;  // 可以前面提前判断，如果sum为奇数，返回false}
};