【代码随想录】刷题笔记Day43-Toy模板网

这篇具有很好参考价值的文章主要介绍了【代码随想录】刷题笔记Day43。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

刚过完非常愉快的元旦假期，唔想反工啊啊啊，先刷刷题找回学习的状态吧

416. 分割等和子集 - 力扣（LeetCode）

dp[target] == target为目标，weight和value相同的01背包问题，用一维遍历
dp[j]为容量为j的背包所能装的最大价值
dp[j] = max(dp[j], dp[j - num[i]] + nums[i])

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        // 也可以使用库函数一步求和
        // int sum = accumulate(nums.begin(), nums.end(), 0);
        for(int num : nums) sum += num;
        // 和为奇数直接返回false
        if(sum % 2 == 1) return false;  
        // 最大容量只需要target就够了
        int target = sum / 2;
        vector<int> dp(target + 1);
        // 开始 01背包
        for(int i = 0; i < nums.size(); i++){
            for(int j = target; j >= nums[i]; j--){
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        // 集合中的元素正好可以凑成总和target
        return dp[target] == target;
    }
};

1049. 最后一块石头的重量 II - 力扣（LeetCode）

关键在于把两两相减问题转化为两堆近似相减，和上一题就极其相似了

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(int num : stones) sum += num;
        int target = sum / 2;
        vector<int> dp(target + 1);
        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]);
            }
        }
        // 两堆相减，sum - dp[target] 减去 dp[target]
        return sum - 2 * dp[target];
    }
};

494. 目标和 - 力扣（LeetCode）

依然是转化为两堆数left和right，通过数学关系left = (target + sum) / 2，如果不能整除说明找不到就直接return 0，于是问题转化为装满背包容量为left有多少种可能
dp[j]：装满容量为j的背包有dp[j]种方法
组合类问题的递推公式：dp[j] += dp[j - nums[i]]
初始化：dp[0] = 1，其他为0

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(int num : nums) sum += num;
        if(abs(target) > sum) return 0;
        if((sum + target) % 2 == 1) return 0;
        int left = (sum + target) / 2;
        vector<int> dp(left + 1);
        dp[0] = 1;
        for(int i = 0; i < nums.size(); i++){
            for(int j = left; j >= nums[i]; j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left];
    }
};