leetcode-notes-20230916

416. 分割等和子集（C++动态规划实现）

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        //思路：背包的体积为sum/2
        //每个元素既是重量又是价值
        //dp[j]表示对于容量为j的背包，其能装的物体最大价值是dp[j]
        //确定递推公式：
        //dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        //最终判断的标准：
        //如果dp[target] == target，那么返回true，否则返回false；

        //初始化动态规划数组
        //题目中指定数组中元素的大小不会超过200，长度不会超过100，所以综合不会超过20000，那么
        //sum / 2 = target == 10000
        //因此定义动态规划数组的长度为10001
        vector<int> dp(10001, 0);

        int sum = 0;
        for(int i = 0;i < nums.size();i++){
            sum += nums[i];
        }

        //判断sum / 2余数是否为1，如果为1，直接返回false；
        if(sum % 2 == 1){
            return false;
        }

        //得到背包最大容量
        int target = sum / 2;

        //开始递推更新dp数组
        //外层循环遍历物体重量
        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]);
            }
        }

        //判断dp[target] == target
        if(dp[target] == target){
            return true;
        }

        return false;
    }
};

1049. 最后一块石头的重量 II（C++动态规划实现）

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        //思路：stones[i]表示第i块石头的重量，价值也为stones[i]
        //题目中说的最小的重量，也就是说将这两堆石头尽可能地分为两份相同的重量
        //那么这道题目就和分割等和子集一样了

        int sum = 0;
        for(int i = 0;i < stones.size();i++){
            sum += stones[i];
        }

        int target = sum / 2;

        //初始化dp数组
        //由于题目中给出stones数组长度最大为30，每个石头最大重量为100
        //30 * 100 = 3000
        //那么，target = sum / 2 = 3000 / 2 = 1500
        vector<int> dp(1501, 0);


        //更新dp数组
        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]);
            }
        }

        return sum - dp[target] - dp[target];
    }
};

494. 目标和（C++动态规划实现）

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        //思路：假设left - right = target，且left + right = sum
        //那么，right = sum - left;
        //则有left - (sum - left) = target
        //left * 2 = sum + target
        //left = (target + sum) / 2
        //所以，原题目变成了求nums[i]数组中元素相加等于(target + sum) / 2的元素和
        //需要注意的是：(target + sum) / 2可能向下取整，这个时候就返回0，表示不存在对应的表达式
        //还有如果target > sum，也是不存在的
        //dp[j]表示能将j容量背包填满的方案数为dp[j]
        //其中，dp[j]应该由dp[j - nums[i]]得到，其中nums[i]是元素i的重量
        //也就是说，只要能找到nums[i]，就能找到dp[j - nums[i]] + nums[i] = dp[j]

        //同时，dp[0]还应该初始化为1
        //因为：对于nums = {0, 0, 0}，(target + sum) / 2，其中target = 0
        //此时，实际上的不同表达式数目为2 * 2 * 2，而结果8的获得肯定是由dp[0] = 1递推得到的，
        //因为如果dp[0] = 0，那么最终得到的dp[j]肯动都是0，因此，dp[0]应当初始化为1

        int sum = 0;
        for(int i = 0;i < nums.size();i++){
            sum += nums[i];
        }

        if(sum < abs(target)){
            return 0;
        }

        if((target + sum) % 2 == 1){
            return 0;
        }


        //得到背包的目标容量为bagSize
        int bagSize = (target + sum) / 2;
        //初始化数组都为0
        vector<int> dp(bagSize + 1, 0);
        //初始化dp[0] = 1
        dp[0] = 1;

        //进行遍历
        for(int i = 0;i < nums.size();i++){
            for(int j = bagSize;j >= nums[i];j--){
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[bagSize];
    }
};