# My DP solution with explanation

• Dp solution, O(n) space ,O(n) time.
create a vector Dp, where Dp[i] = max(Dp[i-1], Dp[i-2]+num[i]). Because there are two choices,rob ith house or not,and they are two subproblems, so Dp solution is effective.

``````class Solution {
public:
int rob(vector<int> &num) {
int len = num.size();
if( len == 0 )
return 0;
vector<int> Dp(len,0);
Dp[0] = num[0];
for( int i = 1; i < len; i++ )
Dp[i] = max(Dp[i-1], i-2 >= 0 ? Dp[i-2] + num[i]:num[i]);
return Dp[len-1];
}
};``````

• This post is deleted!

• O(1) space solution

``````class Solution {
public:
int rob(vector<int> &num) {
int len = num.size();
if( len == 0 )
return 0;
int f1 = num[0],f2 = 0;
for( int i = 1; i < len; i++ )
{
f2 = max(f1, num[i]+ f2);
swap( f1, f2 );
}
return f1;
}
};``````

• ``````public int rob(int[] num) {
int n = num.length;
if(n == 0) return 0;
int[] max = new int[n + 2];
max[0] = 0;
max[1] = 0;
max[2] = num[0];
for(int i = 1; i < n; i++) {
max[i + 2] = Math.max(max[i], max[i - 1]) + num[i];
}
return Math.max(max[n], max[n + 1]);
}
``````

When we traverse houses, we use a array to record the max we can rob until the last rob house. So max[i] =( max[i - 2], max[i -3]) + num[i], we must choose one from the previous three houses.

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