# Intuitive Python DP Solution (one loop)

• Two cases:

1. Don't rob last house, then it becomes a House Robber I problem from House 1 to House n-1.
2. Don't rob first house, then it becomes a House Robber I problem from House 2 to House n.
``````class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0;
elif len(nums) == 1:
return nums[0];
elif len(nums) == 2:
return max(nums[0],nums[1]);
elif len(nums) == 3:
return max(nums[0],nums[1],nums[2]);

dp1 = [0] * (len(nums)-1);
dp2 = [0] * (len(nums)-1);

dp1[0] = nums[0];
dp1[1] = max(nums[0],nums[1]);
dp2[0] = nums[1];
dp2[1] = max(nums[1],nums[2]);

for i in xrange(2,len(nums)-1):
dp1[i] = max(dp1[i-1],dp1[i-2]+nums[i]);
dp2[i] = max(dp2[i-1],dp2[i-2]+nums[i+1]);

return max(dp1[-1],dp2[-1]);

``````

• why dp2[i] = max(dp2[i-1],dp2[i-2]+nums[i+1]);?

according to your description, shouldn't it be dp2[i+1] = max(dp2[i-1],dp2[i-2]+nums[i+1]);

• @hamster "dp1" and "dp2" have same size, the only difference is how to capture the previous house from "nums" because they have different starts (i.e. dp1[0] refers to House 1 which is nums[0], dp2[0] refers to House 2 which is nums[1]).

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