C++ Simple DP & DFS


  • 0
    F
    // O(2*sum*n) DP
    class Solution {
    public:
        int findTargetSumWays(vector<int>& nums, int target) {
            int sum = accumulate(nums.begin(), nums.end(), 0);
            if (target < -sum || target > sum)
                return 0;
            vector<int> dp(sum * 2 + 1), next_dp(sum * 2 + 1);
            dp[sum] = 1;
            for (int i = 1; i <= nums.size(); ++ i)
            {
                for (int j = sum; j >= -sum; -- j)
                {
                    int idx = j + sum;
                    if (idx - nums[i - 1] >= 0)
                        next_dp[idx] = dp[idx - nums[i - 1]];
                    if (idx + nums[i - 1] < sum * 2 + 1)
                        next_dp[idx] += dp[idx + nums[i - 1]];
                }
                swap(dp, next_dp);
            }
            return dp[target + sum];
        }
    };
    
    //O(2^n) DFS
    class Solution {
        int solve(vector<int> const & nums, int target, int k)
        {
            if (k < 0)
                return target == 0;
            return solve (nums, target - nums[k], k - 1) + solve (nums, target + nums[k], k - 1);
        }
    public:
        int findTargetSumWays(vector<int> const & nums, int target) {
            return solve(nums, target, (int)nums.size() - 1);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.