408算法题leetcode--第37天

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 / 2
        int 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
    }
};