leetcode 494 目标和

怼烎@ 2022-08-28 04:57 144阅读 0赞

## 前言 ##

题目：[494. 目标和][494.]

参考题解：[494. 目标和][494. 1]

--------------------

## 提交代码 ##

这道题目挺难。

### 错误的动态规划 ###

下面代码是我第一次提交的代码。它的思路见注释。这个思路在最后一步存在错误，后面有正确代码。

#include <vector>
    #include <iostream>
    
    using namespace std;
    
    class Solution {
    public:
        int findTargetSumWays(vector<int>& nums, int target) {
            /**
             * 思路：1.先将所有的值转换成正整数。
             *      2.求和，用和减去target。
             *      3.剩余值如果正好可以分两半，则满足要求
             *      4.步骤3可以通过01背包问题实现。其中，背包大小为剩余值的一半
             *      5.可能出现多次满足要求的情况，每次出现都记录下
             * */ 
    
            /**
             * 该思路错误。反例：[2,1,3,5,2,1,4,5,8,3,1,4]， target=3
             * 输出6； 预期结果为238
            */
    
            // 全部转换成正整数，并求和
            int sum = 0;
            for(int i=0; i<nums.size(); i++){
                if(nums[i]<0)
                    nums[i] = -nums[i];
                sum += nums[i];
            }
    
            // 背包大小
            if(sum-target == 0){ //全部数字用于抵消target:
                int result = 0;
                for(auto num : nums)
                    num == 0 ? result++:result;
                return result == 0 ? 1:result*2;
            }
            if((sum-target)%2 != 0)
                return 0;
            int bag_weight = (sum-target)/2;
    
            int result = 0;
            vector<int> dp(bag_weight+1,0);
            for(int i=0; i<nums.size(); i++){ // 遍历物品
                for(int j=bag_weight; j>=nums[i]; j--){ // 遍历背包
                    // dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
                    if(dp[j-nums[i]]+nums[i] >= dp[j]){ // 放这件物品
                        dp[j] = dp[j-nums[i]]+nums[i];
                        if(dp[j]==bag_weight) // 遇到一种满足要求哒
                            result++;
                    }
                }
                // for(int i=0; i<=bag_weight; i++)
                //     cout<<dp[i]<<" ";
                // cout<<endl;
            }
    
            return result;
        }
    };
    
    int main(void){
        vector<int> nums = {1,0,0};
        int target = 1;
        Solution s;
        cout<<s.findTargetSumWays(nums,target);
    }

### 正确的动态-滚动数组实现 ###

看完参考题解之后，我重新写了一遍。

注意，这道题目运行物品的重量为零。必须理解滚动的过程中，重量为零是如何处理的，才能明白这个动态规划。

#include <vector>
    #include <iostream>
    
    using namespace std;
    
    class Solution {
    public:
        int findTargetSumWays(vector<int>& nums, int target) {
            /**
             * 思路：1.先将所有的值转换成正整数。
             *      2.求和，用和减去target。
             *      3.剩余值如果正好可以分两半，则满足要求
             *      4.步骤3可以通过01背包问题实现。其中，背包大小为剩余值的一半
             *      5.背包问题，动态规划。其中，dp[j]表示，装满容量为j背包的方法有的dp[j]中。滚动数组中，dp[j] += dp[j-nums[i]]
             * */ 
    
            int sum = 0;
            for(int i=0; i<nums.size(); i++){
                if(nums[i]<0)
                    nums[i] = -nums[i];
                sum += nums[i];
            }
            
            if( sum-abs(target)<0 || (sum-abs(target))%2 != 0)
                return 0;
            int bag_weight = (sum-abs(target))/2;
    
            vector<int> dp(bag_weight+1,0);
            dp[0] = 1; // 表，东西全部装入
            // dp[nums[0]]=1; // 在循环里面，会被正确赋值
            for(int i=0; i<nums.size(); i++){ // 遍历物品
                for(int j=bag_weight; j>=nums[i]; j--){ // 遍历背包
                        dp[j] += dp[j-nums[i]]; // 如果nums[i]为零，将自己翻倍。因为0的正负都不影响
                    }
            }
    
            return dp[bag_weight];
        }
    };
    
    int main(void){
        vector<int> nums = {2,107,109,113,127,131,137,3,2,3,5,7,11,13,17,19,23,29,47,53};
        int target = 1000;
        Solution s;
        cout<<s.findTargetSumWays(nums,target);
    }

### 动态规划-二维数组 ###

**这道题目，我不推荐使用滚动数组。因为太巧妙了**。

滚动数组的递推公式`dp[j] = dp[j] + dp[j-nums[i]]`有三种含义(三种每次只有一个成立)：

1.  不包含当前元素，前i-1件物品，正好装满j背包的方法数目。方法数目==等号右侧的dp\[j\]。
2.  包含当前元素，前i件物品，正好装满j背包的方法数目。
    
    2.1 如果这个物品的重量不为零，常规情况，到滚动数组的前面去查找。方法数目为dp\[j-nums\[i\]\]  
    2.1 如果这个物品的重量为零，由于零的正负均可，所以方法翻倍，此时dp\[j\]为原来dp\[j\]的两倍。

那这道题目，使用二维数组该如何实现呢？

下面为我实现的代码。

#include <vector>
    #include <algorithm>
    #include <iostream>
    
    using namespace std;
    
    class Solution {
    public:
        int findTargetSumWays(vector<int>& nums, int target) {
            int sum = 0;
            int zero_cnt=0;
            for(auto num : nums){
                sum += num;
                if(num==0)
                    zero_cnt++;
            }
            target = abs(target);
            if(sum-target<0 || (sum-target)%2!=0) // 所有的装入都不够；或者扣除装入之后，剩余的不能均分
                return 0;
            // int bag_weight = (sum - target)/2;
            int bag_weight = (sum + target)/2;
    
            // dp[i][j]表示，在[0,i]物品中，装满j容量的方法数目
            // 初始化行：dp[0][nums[0]] = 1;第一个物品恰好装满
            // 初始化列：dp[x][0]=1; 此时背包容量为零，表示所有物品全部需要(sum==target)，所以只有一种方法
            vector<vector<int>> dp(nums.size(),vector<int>(bag_weight+1,0));
            dp[0][nums[0]] = 1;
            for(int i=0; i<nums.size(); i++)
                dp[i][0] = 1;
    
            for(int i=1; i<nums.size(); i++){ // 遍历物品
                for(int j=1; j<=bag_weight; j++){ // 遍历背包
                    if(j<nums[i])
                        dp[i][j] = dp[i-1][j]; // 装不下，只好继承，使用前i-1件装满j容量；
                    else{
                        if(nums[i]!=0)
                            dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]; // 不装当前元素，使用前i-1件装满j容量 +  使用当前元素，使用前i件装满j容量 
                        else{
                            dp[i][j] = dp[i-1][j]; // 如果是0，我们当没看见这个元素
                        }
                    }
                }
            }
    
            for(auto vec : dp){
                for(auto v : vec)
                    cout<<v<<" ";
                cout<<endl;
            }
    
            return dp[nums.size()-1][bag_weight]*(1<<zero_cnt); // 0的正负都不影响结果，正负均可
        }
    };
    
    int main(void){
        vector<int> nums = {0,0,0,0,0,0,0,0,1};
        int target = 1;
    
        // vector<int> nums = {1,0,0};
        // int target = 1;
    
        Solution s;
        cout<<s.findTargetSumWays(nums,target);
    }

### 回溯 ###

本题当然也可以使用回溯法，进行暴力破解。

我想去吃饭，代码没有写。可参考：[leetcode 39 组合总和][leetcode 39]

[494.]: https://leetcode-cn.com/problems/target-sum/
[494. 1]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.md
[leetcode 39]: https://blog.csdn.net/sinat_38816924/article/details/120463376