[Day 23] Leetcode 494. Target Sum (C++)

前言

今天这题也是top 100 liked的题目─494. Target Sum。虽然是medium，但我觉得很难QQ 一开始写的dfs虽然过了，但颇没有效率，花了非常久的时间想去弄懂官方解答跟各种神人的dp解，就来一起看看吧！

想法

这题我的第一个想法是先把题目变单纯一点，用目前的sum去减去target，获得的东西/2就变成了任选几个elements组成新的sum的题目，而我这个算法新的sum代表是任选几个把他们的符号变成-的。若把目前的(sum+target)/2，这个就是任选几个前面的符号变成+的题目。
依此概念，我写出了一个dfs解，不过颇没有效率，还有待研究优化方式，如下：
概念说明：排序後从第一个开始选，去後面dfs确认任选後面不同的结果是否可达到sum

class Solution {
public:
    void helper(vector<int>& nums, int target, int k, int &ans){
        if(target==0){
            ++ans;
        }
        for(int i=k;i<nums.size();++i){
            if(target<nums[k]){
                return;
            }
            helper(nums, target-nums[i], i+1, ans);
        }
    }
    
    int findTargetSumWays(vector<int>& nums, int target) {
        // turn the problem to unsigned target sum
        // compute the sum 
        int sum=0;
        for(int i=0;i<nums.size();++i){
            sum+=nums[i];
        }
        int targetNew = (sum-target)/2;
        if ((sum-target)%2!=0){
            return 0;
        }
       
        // use DFS to search for answer
        sort(nums.begin(),nums.end());
        int ans=0;
        helper(nums, targetNew, 0, ans);
        
        return ans;

    }
};

不过重点是来研究dp解到底要怎麽做呢？
我们先从比较可以理解的2维DP开始看。
首先跟前面一样先算出new target，采用(sum+target)/2的方式来算需要取哪几个元素为+。
而重点是DP的递回，用二维的table来记录，一维是从~第i个nums挑选，nums[0:i]的组合，第二维是加总为多少，里面存的值就是有几种组合。初始就是二维为0的都是1，就是什麽都不选。开始更新就从i只有一个开始，j直接从0开始，到new target为止。然後从开始去找要不要加这个数，加了nums[i]之後代表每个nums[i-1][j]次数=nums[i-1][j-nums[i]]+nums[i-1][j]，後面代表不加。
程序码如下：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        // compute the nums sum to avoid some impossible cases and compute for new target
        int sum = accumulate(nums.begin() , nums.end() , 0);
        // cut down on some impossible answers
        // not enough or always too big or not possible 
        if(sum<target || -sum>target || (sum+target)%2!=0){
            return 0;
        }       
        // all should be used => trap!! if there are 0s, there are multiple answers
        //if(sum==target || sum==-target){
        //    return 1;
        //}
        // compute for how much the positive sums should be (-negative sum=target)
        int targetNew = (target + sum)/2;
        // use 2d dp[i][j] to save the nums[0:i] sums to j counts
        vector<vector<int>> dp(nums.size()+1,vector<int>(targetNew+1,0));
        // i=0, j=0 => not choosing any elements and the sum is 0
        dp[0][0] = 1;
        //for(int i=0;i<nums.size();++i){
        //    dp[i][0]=1;
        //}
        
        for(int i=1;i<=nums.size();++i){
            // for every sum, update its count
            for(int j=0;j<=targetNew;++j){
                //cout<<i<<j<<endl;
                // nums[i] chosen count + not chosen count
                if((j-nums[i-1])>=0){
                    dp[i][j] = dp[i-1][j-nums[i-1]] + dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
                
            }
        }
        return dp[nums.size()][targetNew];
        
    }
};

还可以优化为1维的DP来节省空间，但先理解到这里为止吧XD

结语

sum系列真的非常多，又经典又有挑战性，就继续sum系列吧！