# C++ solution with dp

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

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

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