# 0ms C++ dp solution with explanation

• robs(k) = max( robs(k-2), rob(k-3) ) + nums(k);

In the 1st pass, I didn't calculate the N-1 element;

In the 2nd pass, I didn't calculate the N-2 element;

The final result is the max of the two pass.

``````class Solution {
public:
int rob(vector<int>& nums) {
const int N = nums.size();
if(0 == N) return 0;
if(1 == N) return nums[0];
if(2 == N) return max(nums[0], nums[1]);
if(3 == N) return max(max(nums[0], nums[1]), nums[2]);
vector<int> robs(N, 0);

//the 1st pass
robs[0] = nums[0];
robs[1] = nums[1];
robs[2] = nums[0] + nums[2];
for(int i = 3; i < N -1;  ++i){
robs[i] = max(robs[i-2], robs[i-3]) + nums[i];
}
int max1 = max(robs[N-2], robs[N-3]);

//the 2nd pass
robs[0] = nums[0];
robs[1] = nums[1] + nums[N-1];
robs[2] = max(nums[0], nums[N-1]) + nums[2];
for(int i = 3; i < N -2;  ++i){
robs[i] = max(robs[i-2], robs[i-3]) + nums[i];
}
int max2 = max(robs[N-3], robs[N-4]);
return max(max1, max2);
}
};``````

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