5 Lines Easy DP solution in C++


  • 0
    S

    Given in problem that if we choose N then N-1 and N+1 should be deleted. In other way it means if we want to pick i , then maximum sum till 'i' will be maximum of('sum till i-2 + frequency of ith element * i' ,'sum till i-1'). This gives easy DP expression as
    *'dp[i] = max(dp[i-1],dp[i-2]+(cnt[i]i))'

    where array 'cnt[]' holds count of 'i' in array 'nums' . i.e 'i' will contribute 'i*cnt[i]' in total sum;
    and dp[i] holds maximum sum till i

    class Solution {
    public:
        int deleteAndEarn(vector<int>& nums) {
            vector<int> cnt(10009,0);
            int n = nums.size();
    
            for(int i=0;i<n;i++)cnt[nums[i]]++;// store the frequency of i'th element of nums in array cnt
    
            vector<int> dp(10009,0);
    
            dp[1] = cnt[1]*1;// as maximum sum till 1 will be cnt[1] i.e frequency of 1 in nums[]
    
            for(int i=2;i<=10000;i++)
            {
                dp[i]=max(dp[i-1],dp[i-2]+(cnt[i]*i));//maximum sum till i'th element according to above dp expression
            }
            return dp[10000];
        }
    };
    

  • 1

    Um... how is that "5 Lines"?


  • 0
    S

    @ManuelP
    if you dont count function signature, variable declaration , its of 5 lines only

    line 1: for(int i=0;i<n;i++)cnt[nums[i]]++;
    line 2: dp[1] = cnt[1]*1;
    line 3: for(int i=2;i<=10000;i++)
    line 4: dp[i]=max(dp[i-1],dp[i-2]+(cnt[i]*i));
    line 5: return dp[10000];
    

    just count the algorithmic steps only


  • 0

    @shaeli Hmm, not counting the signature is common (regarded as part of the question, not part of the actual solution), but not counting your own variable declarations (and even non-default definitions!) is very uncommon and unexpected, so this is rather misleading...


  • 0

    Btw, better don't format everything as code, makes your explanation hard to read, especially the need to scroll it sideways.

    Oh and you're accessing dp[i-2] even when i = 1, i.e., dp[-1]. That's not good.


  • 0
    S

    @shaeli said in 5 Lines Easy DP solution in C++:

    Given in problem that if we choose N then N-1 and N+1 should be deleted. In other way it means if we want to pick i , then maximum sum till 'i' will be maximum of('sum till i-2 + frequency of ith element * i' ,'sum till i-1'). This gives easy DP expression as
    *'dp[i] = max(dp[i-1],dp[i-2]+(cnt[i]i))'

    where array 'cnt[]' holds count of 'i' in array 'nums' . i.e 'i' will contribute 'i*cnt[i]' in total sum;
    and dp[i] holds maximum sum till i

    class Solution {
    public:
        int deleteAndEarn(vector<int>& nums) {
            vector<int> cnt(10009,0);
            int n = nums.size();
    
            for(int i=0;i<n;i++)cnt[nums[i]]++;// store the frequency of i'th element of nums in array cnt
    
            vector<int> dp(10009,0);
    
            dp[1] = cnt[1]*1;// as maximum sum till 1 will be cnt[1] i.e frequency of 1 in nums[]
    
            for(int i=2;i<=10000;i++)
            {
                dp[i]=max(dp[i-1],dp[i-2]+(cnt[i]*i));//maximum sum till i'th element according to above dp expression
            }
            return dp[10000];
        }
    };
    

Log in to reply
 

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