Evolve from brute force to dp


  • 14

    This is similar to Partition Equal Subset Sum.

    1. O(2^n) brute force
        int findTargetSumWays(vector<int>& nums, int S) {
            return find(0,nums,S);    
        }
        int find(int p, vector<int>& nums, int sum) {
            if(p==nums.size()) return sum==0;
            return find(p+1,nums,sum+nums[p])+find(p+1,nums,sum-nums[p]);
        }
    
    1. O(ns) Memoization. There is redundancy in brute force. A call to find() with the same start index and target sum can be made multiple times. We can use a 2d table to cache the result to avoid duplicate calls with the same state.
        int findTargetSumWays(vector<int>& nums, int S) {
            vector<unordered_map<int,int>> mem(nums.size());
            return find(0,nums,S,mem);    
        }
        int find(int p, vector<int>& nums, int sum, vector<unordered_map<int,int>>& mem) {
            if(p==nums.size()) return sum==0;
            auto it = mem[p].find(sum);
            if(it != mem[p].end()) return it->second;
            return mem[p][sum]=find(p+1,nums,sum+nums[p],mem)+find(p+1,nums,sum-nums[p],mem);
        }
    
    1. O(ns) pseudo polynomial dp, s is the target sum. Most dp problems visits continuous states and this is a great example to use hashtable to visit valid states only.
        int findTargetSumWays(vector<int>& nums, int S) {
            int n = nums.size();
            vector<unordered_map<int,int>> dp(n+1);
            dp[0][0]=1;
            for(int i=0;i<n;i++)
                for(auto &p:dp[i]) {
                    dp[i+1][p.first+nums[i]] += p.second; 
                    dp[i+1][p.first-nums[i]] += p.second;
                }
            return dp[n][S];
        }
    
    1. O(ns) time, linear space dp.
        int findTargetSumWays(vector<int>& nums, int S) {
            unordered_map<int,int> cur({{0,1}}), nxt, *p_cur=&cur, *p_nxt=&nxt;
            for(int i=0;i<nums.size();i++) {
                for(auto &p:*p_cur) {
                    (*p_nxt)[p.first+nums[i]] += p.second; 
                    (*p_nxt)[p.first-nums[i]] += p.second;
                }
                swap(p_cur,p_nxt);
                p_nxt->clear();
            }
            return (*p_cur)[S];
        }
    
    1. O(ns) dp with continuous states. When hashtable is replaced by vector, test cases show significant runtime improvement. #4 is theoretically better because it does not visit invalid states.
        int findTargetSumWays(vector<int>& nums, int S) {
            int sum = accumulate(nums.begin(),nums.end(),0);
            if(S>sum || S<-sum) return 0;
            vector<int> cur(2*sum+1), nxt(2*sum+1), *p_cur = &cur, *p_nxt = &nxt;
            cur[sum] = 1;
            for(int i=0;i<nums.size();i++) {
                for(int j=0;j<=2*sum;j++) 
                    if(p_cur->at(j)) {
                        p_nxt->at(j+nums[i]) += p_cur->at(j);
                        p_nxt->at(j-nums[i]) += p_cur->at(j);
                    }
                swap(p_cur,p_nxt);
                p_nxt->assign(2*sum+1,0);
            }
            return p_cur->at(S+sum);
        }
    

  • 0
    S

    @yu6 Thanks.
    What is s in your time complexity? Like O(ns) in #2 and #3?
    Can #3 still be called a DP? I would rather call it an iterative method.


  • 0

    @shuhua s is the target sum.
    It is dp because it breaks the problem into subproblmes and solves each subproblem only once.


  • 0

    @yu6 said in Evolve from brute force to dp:

    if(p==nums.size()) return sum==0;

    I'm not familiar with C++ advanced syntax, is it returning an integer? Looks like an Equality operator.


  • 0

    @new2500 It returns 1/0 for true/false


  • 0

    @yu6 said in Evolve from brute force to dp:

    This is similar to Partition Equal Subset Sum.

    1. O(2^n) brute force
        int findTargetSumWays(vector<int>& nums, int S) {
            return find(0,nums,S);    
        }
        int find(int p, vector<int>& nums, int sum) {
            if(p==nums.size()) return sum==0;
            return find(p+1,nums,sum+nums[p])+find(p+1,nums,sum-nums[p]);
        }
    
    1. O(ns) Memoization. There is redundancy in brute force. A call to find() with the same start index and target sum can be made multiple times. We can use a 2d table to cache the result to avoid duplicate calls with the same state.
        int findTargetSumWays(vector<int>& nums, int S) {
            vector<unordered_map<int,int>> mem(nums.size());
            return find(0,nums,S,mem);    
        }
        int find(int p, vector<int>& nums, int sum, vector<unordered_map<int,int>>& mem) {
            if(p==nums.size()) return sum==0;
            auto it = mem[p].find(sum);
            if(it != mem[p].end()) return it->second;
            return mem[p][sum]=find(p+1,nums,sum+nums[p],mem)+find(p+1,nums,sum-nums[p],mem);
        }
    
    1. O(ns) pseudo polynomial dp, s is the target sum. Most dp problems visits continuous states and this is a great example to use hashtable to visit valid states only.
        int findTargetSumWays(vector<int>& nums, int S) {
            int n = nums.size();
            vector<unordered_map<int,int>> dp(n+1);
            dp[0][0]=1;
            for(int i=0;i<n;i++)
                for(auto &p:dp[i]) {
                    dp[i+1][p.first+nums[i]] += p.second; 
                    dp[i+1][p.first-nums[i]] += p.second;
                }
            return dp[n][S];
        }
    
    1. O(ns) time, linear space dp.
        int findTargetSumWays(vector<int>& nums, int S) {
            unordered_map<int,int> cur({{0,1}}), nxt, *p_cur=&cur, *p_nxt=&nxt;
            for(int i=0;i<nums.size();i++) {
                for(auto &p:*p_cur) {
                    (*p_nxt)[p.first+nums[i]] += p.second; 
                    (*p_nxt)[p.first-nums[i]] += p.second;
                }
                swap(p_cur,p_nxt);
                p_nxt->clear();
            }
            return (*p_cur)[S];
        }
    
    1. O(ns) dp with continuous states. When hashtable is replaced by vector, test cases show significant runtime improvement. #4 is theoretically better because it does not visit invalid states.
        int findTargetSumWays(vector<int>& nums, int S) {
            int sum = accumulate(nums.begin(),nums.end(),0);
            if(S>sum || S<-sum) return 0;
            vector<int> cur(2*sum+1), nxt(2*sum+1), *p_cur = &cur, *p_nxt = &nxt;
            cur[sum] = 1;
            for(int i=0;i<nums.size();i++) {
                for(int j=0;j<=2*sum;j++) 
                    if(p_cur->at(j)) {
                        p_nxt->at(j+nums[i]) += p_cur->at(j);
                        p_nxt->at(j-nums[i]) += p_cur->at(j);
                    }
                swap(p_cur,p_nxt);
                p_nxt->assign(2*sum+1,0);
            }
            return p_cur->at(S+sum);
        }
    

Log in to reply
 

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