Evolve from recursion to dp


  • 1
    1. Recursion O(n^(target/min(nums))
        int combinationSum4(vector<int>& nums, int target) {
            if(target<=0) return !target?1:0;
            int ct=0;
            for(int i=0;i<nums.size();i++) ct+=combinationSum4(nums, target-nums[i]);
            return ct;
        }
    
    1. memoization O(n*target)
        int combinationSum4(vector<int>& nums, int target) {
            vector<int> mem(target+1,-1);
            return dfs(target,mem,nums);
        }
        int dfs(int target, vector<int>& mem, vector<int>& nums) {
            if(target<=0) return !target?1:0;
            if(mem[target]!=-1) return mem[target];
            int ct=0;
            for(int i=0;i<nums.size();i++) ct+=dfs(target-nums[i],mem,nums);
            return mem[target] = ct;
        }
    
    1. dp O(n*target), This is slower than memoization because memorization does not compute all from 1 to target.
        int combinationSum4(vector<int>& nums, int target) {
            vector<int> dp(target+1);
            dp[0]=1;
            for(int i=1;i<=target;i++) 
                for(int j=0;j<nums.size();j++) 
                    if(i >= nums[j]) dp[i] += dp[i-nums[j]];
            return dp[target];
        }
    
    1. dp O(n*target), early termination
        int combinationSum4(vector<int>& nums, int target) {
            vector<int> dp(target+1);
            dp[0]=1;
            sort(nums.begin(),nums.end());
            for(int i=1;i<=target;i++) 
                for(int j=0;j<nums.size();j++) 
                    if(i >= nums[j]) dp[i] += dp[i-nums[j]];
                    else break;
            return dp[target];
        }
    

  • 1
    H

    Hi
    I was wondering why is the complexity O(2^(target/min(nums))
    At each node, we can recurse n times..
    And we can go as deep as target..
    Thus, it might be O(n^target).
    Of course, your bound is much tighter and I was wondering how did you derive that

    Thanks


  • 0

    @henry19 You are right. It is a typo O(2^(target/min(nums)) should be O(n^(target/min(nums)). Thanks for picking it out


Log in to reply
 

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