# Easy to understand Python solutions (Dynamic Programming).

• ``````# O(n) space
def rob1(self, nums):
if not nums:
return 0
if len(nums) <= 2:
return max(nums)
res = [0] * len(nums)
res[0], res[1] = nums[0], max(nums[0], nums[1])
for i in xrange(2, len(nums)):
res[i] = max(nums[i]+res[i-2], res[i-1])
return res[-1]

def rob2(self, nums):
if not nums:
return 0
res = [0] * len(nums)
for i in xrange(len(nums)):
if i == 0:
res[0] = nums[0]
elif i == 1:
res[1] = max(nums[0], nums[1])
else:
res[i] = max(nums[i]+res[i-2], res[i-1])
return res[-1]

# Constant space
def rob(self, nums):
if not nums:
return 0
if len(nums) <= 2:
return max(nums)
a, b = nums[0], max(nums[0], nums[1])
for i in xrange(2, len(nums)):
tmp = b
b = max(nums[i]+a, b)
a = tmp
return b``````

• O(1) space solution:

``````def rob(self, nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
cur = nums[0]
pre = max(nums[:2])
for i in xrange(2, len(nums)):
cur = max(cur+nums[i], pre)
cur, pre = pre, cur
return pre``````

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