• Time:O(n)
• Space:O(n)

## C++

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

// dp[i] := max money of robbing nums[0..i]
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

for (int i = 2; i < nums.size(); ++i)
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);

return dp.back();
}
};
``````

## JAVA

``````class Solution {
public int rob(int[] nums) {
final int n = nums.length;
if (n == 0)
return 0;
if (n == 1)
return nums[0];

// dp[i] := max money of robbing nums[0..i]
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);

for (int i = 2; i < n; ++i)
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);

return dp[n - 1];
}
}
``````

## Python

``````class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]

# dp[i]: = max money of robbing nums[0..i]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

return dp[-1]
``````

• Time:O(n)
• Space:O(1)

## C++

``````class Solution {
public:
int rob(vector<int>& nums) {
int prev1 = 0;  // dp[i - 1]
int prev2 = 0;  // dp[i - 2]

for (const int num : nums) {
const int dp = max(prev1, prev2 + num);
prev2 = prev1;
prev1 = dp;
}

return prev1;
}
};
``````

## JAVA

``````class Solution {
public int rob(int[] nums) {
int prev1 = 0; // dp[i - 1]
int prev2 = 0; // dp[i - 2]

for (final int num : nums) {
final int dp = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = dp;
}

return prev1;
}
}
``````

## Python

``````class Solution:
def rob(self, nums: List[int]) -> int:
prev1 = 0  # dp[i - 1]
prev2 = 0  # dp[i - 2]

for num in nums:
dp = max(prev1, prev2 + num)
prev2 = prev1
prev1 = dp

return prev1
``````