C++ DP solution


  • 1
    S
    class Solution {
    public:
        int rob(vector<int>& nums) {
            int n=nums.size();
            if(n==0) return 0;
            if(n==1) return nums[0];
            nums[1] = max(nums[1], nums[0]);
            for(int i=2; i<n; i++){
                nums[i] = max(nums[i-2]+nums[i], nums[i-1]);
                
            }
            return nums[n-1];
        }
    };

  • 0
    W
    int rob( vector<int>& nums ) {
    		nums.push_back( 0 );
    		vector<int> sum( nums.begin(), nums.end() );
    		for (int i = nums.size() - 3; i >= 0; --i)
    			sum[i] = max( sum[i + 1], sum[i + 2] + nums[i] );
    		return sum[0];
    	}
    

    mine is also a DP solution,but i do it in reverse order.


  • 0
    M
    **c++ 0ms, O(1)space, damn easy solution **   
    
     class Solution {
        public:
            int rob(vector<int>& nums)
            {
                int n=nums.size();
                if(n==0) 
                return 0;
                if(n==1)  
                return nums[0];
                if(n==2)
                return  max(nums[0],nums[1]);
    
                int a=nums[0];
                int b=max(nums[0],nums[1]);
                int c;
                for(int i=2;i<n;i++)
                {
                    c=max(a+nums[i],b);
                    a=b;b=c;
                }
    
                return c;
            }
        };

Log in to reply
 

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