Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode #198: House Robber
class Solution {
public:
int rob(vector<int>& nums) {
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> dp(n+1, 0);
dp[0] = 0;
dp[1] = nums[0];
dp[2] = max(nums[0], nums[1]);
for (int i=3; i<=n; i++) {
dp[i] = nums[i-1] + max(dp[i-2], dp[i-3]);
}
return max(dp[n], dp[n-1]);
}
};
// Note: Space complexity of this solution can be reduced to O(1) by using 3-4 variables instead of an array/vector.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.