Very clean simplified DP solution 0ms in C++ using O(1) space


  • 0

    Brief explanation:

    • there are two different solutions, while the latter one is far better but its perspective is quite different from the first;

    • pre and cur will be the maximal amount of money he can rob till house i-2 and i.


    class Solution {
    private:
        int rob1(vector<int>& nums, int begin, int end) 
        {
            int size = end-begin+1;
            if(size == 1) return nums[begin];
            int robbed[size]{0};
            robbed[0] = nums[begin];
            robbed[1] = nums[begin+1];
            int maxRob = max(robbed[0], robbed[1]);
            for(int i = 2; i < size; ++i) //robbed[i] is the maximum ends with house[i] (house[i] is robbed too);
            {
                robbed[i] = robbed[i-1];
                for(int j = i-2; j >= 0; --j)
                    robbed[i] = max(robbed[i], robbed[j]+nums[i+begin]);
                maxRob = max(maxRob, robbed[i]);
            }
            return maxRob;
        }
    public:
        int rob(vector<int>& nums) 
        {
            int size = nums.size();
            if(!size) return 0;
            if(size == 1) return nums[0];
            return max(rob1(nums, 0, size-2), rob1(nums, 1, size-1));
        }
    
        int rob(vector<int>& nums) 
        {
            int size = nums.size();
            if(size == 0) return 0;
            if(size == 1) return nums[0];
            if(size == 2) return max(nums[0], nums[1]);
            int pre = nums[0], cur = max(nums[0], nums[1]);
            int t = 0, withFirst = 0;    
            for(int i = 2; i < size-1; ++i)
            {
                t = pre;
                cur = max(pre=cur, t+nums[i]); //cur is the maximum till house[i] (house[i] is robbed or not, god knows, we just care about the maximum);
            }
            withFirst = cur;
            pre = nums[1], cur = max(nums[1], nums[2]);
            for(int i = 3; i < size; ++i)
            {
                t = pre;
                cur = max(pre=cur, t+nums[i]);
            }
            return max(withFirst, cur);
        }
    };

Log in to reply
 

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