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


  • 0

    Thanks for your solution~

    Can you please explain how the runtime complexity approach 2 (recursion with memoization) is O(n*target)?


  • 0

    @ramanpreetSinghKhinda It is bottom up recursion. The number of states to compute is O(target). To compute each state, we check all the numbers to get the previous states. So it is O(target*n).


Log in to reply
 

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