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

• 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);
}
};``````

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