C++ solution with dp


  • 0
    B
    class Solution {
    public:
        int rob(vector<int>& nums) {
            int n = nums.size();
            if (n < 1)
            {   
                return 0;
            }
            if (n == 1)
            {
                return nums[0];
            }
    
            int result = 0;
            int buf[n];
            int maxTable[n];
            //select the first
            buf[0] = nums[0];
            maxTable[0] = nums[0];
            buf[1] = nums[1];
            maxTable[1] = nums[0];
    
            for (int i = 2; i < n-1; i++)
            {
                buf[i] = maxTable[i-2] + nums[i];
                maxTable[i] = max(buf[i], maxTable[i-1]);
            }
    
            result = maxTable[n-2];
        
            //do not select the first
            buf[0] = 0;
            maxTable[0] = 0;
            buf[1] = nums[1];
            maxTable[1] = nums[1];
        
            for (int i = 2; i < n; i++)
            {
                buf[i] = maxTable[i-2] + nums[i];
                maxTable[i] = max(buf[i], maxTable[i-1]);
            }
    
            if (maxTable[n-1] > result)
            {
                result = maxTable[n-1];
            }
    
            return result;
        }
    };

  • 0
    Q

    One more solution :

      int rob(vector<int>& nums) 
      {        
        int len=nums.size(), result=0;
        
        if(len==0)
        return 0;
        
        if(len==1)
        return nums[0];
        
        vector<int> s (len+1, 0);
        s[1]=nums[0];
        s[2]=nums[1];
        
        for(int i=3; i<len; i++)
        {
            s[i]=max(s[i-2], s[i-3]) + nums[i-1];
        }
        result = max(s[len-2], s[len-1]);
        
        s[1]=nums[1];
        s[2]=nums[2];
        
        for(int i=3; i<=len; i++)
        {
            s[i]=max(s[i-2], s[i-3]) + nums[i];
        }
        
        return max(result, max(s[len-2], s[len-1]));
      }

Log in to reply
 

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