494. Target Sum(数组中数可正可负求和为S)

港控/mmm° 2023-02-12 07:29 10阅读 0赞

题目描述：  
您将获得非负整数a1，a2，…，an和目标S的列表。现在您有2个符号+和-。对于每一个整数，你应该选择从一个+和-它的新符号。

找出几种分配符号的方法，以使整数和等于目标S。

思路：  
感叹数学的美！fucking amazing。  
计算一个数组里面的值和为s的方法：首先有正有负，sum§-sm(n)=target.化简为 2sum§=target+ sum(nums) （左右两边加sum§+sum(N)——————P是正数部分的和，N是负数部分的和。sum(nums)是整个数组正数的和  
问题转化为求出数组中和为 p的方法数。利用dp带记忆的动态规划。设置dp\[s+1\] 数组，然后从nums中开始遍历，对于每个数num，都从i=S开始，找出每一个对于dp\[ i \] += dp \[ i - num\]。就是每一个数i 能够使得和为该数的方法。  
（因为30-1=29，30-29=1.所以只要其中有1和29就一定可以得30.不用管顺序）

code：

public:
        int findTargetSumWays(vector<int>& nums, int S) { 
            int sum=accumulate(nums.begin(),nums.end(),0);
            
            return sum<S ||  (S+sum)%2 ? 0: sumOfP(nums,(S+sum)>>1);
        }
        
        int sumOfP(vector<int>& nums, int S)
        { 
            vector<int>dp(S+1);
            dp[0]=1;
            
            for(int num: nums)
                for(int i=S; i>=num; --i)
                    dp[i]+=dp[i-num];
            //和为s，并且所有的数都没有超过sum。就转化为两个个数的和。S范围的每个数都和num来计算。关键在 i-num==0后就有了1.
            return dp[S];
        }
            
    };