# C++,My solution,DP

• ``````class Solution {
public:
int rob(vector<int>& nums) {
const int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
if (n == 2) return max(nums[0], nums[1]);
vector<int> f(n, 0);
f[0] = nums[0];
f[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; ++i)
f[i] = max(f[i-2] + nums[i], f[i-1]);
return f[n-1];
}
};``````

• Your solution looks good. But it might fail the test case below:
2, 5, 17, 3, 9, 28, 19, 29, 5, 7, 31
The expected result for this test case should be 2+17+28+29+31 = 107;
But the result of your code will be 5+3+28+29+31 = 96;

• I have tested your case and the result is 107. :)

• Correct, my mistake.

• you can save some space by rotating your cache.

``````class Solution {
public:
int rob(vector<int> &nums) {
int n = nums.size();
if (n == 0) {
return 0;
} else if (n == 1) {
return nums[0];
}

int dp[2] = {nums[0], std::max(nums[0], nums[1])};
for (int i = 2; i < n; ++i) {
dp[i % 2] = std::max(nums[i] + dp[(i - 2) % 2], dp[(i - 1) % 2]);
}
return dp[(n - 1) % 2];
}
};
``````

• said in C++,My solution,DP:

if (n == 2) return max(nums[0], nums[1]);

Nice solution, This line is not needed : )

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