213. House Robber II

Approach 1: Keep track of amount robbed using DP

The approach is very similar to House Robber (which I strongly recommend reading first)

Since the array is circular this time, we will keep track of two lists of sums, one with nums[0] (dpl) and one without nums[0] (dpr). This way when we reach the last element, we will only check the array that does not have nums[0] to make sure that first and the last houses are not robbed together.

class Solution(object):
    def rob(self, nums):
        """
        https://leetcode.com/problems/house-robber-ii/description/
        :type nums: List[int]
        :rtype: int
        """
        lea = len(nums)
        if lea == 0:
            return 0
        if lea == 1:
            return nums[0]
        if lea == 2:
            return max(nums)
        if lea == 3:
            return max(nums[0], nums[1], nums[2])
        if lea == 4:
            return max(nums[1] + nums[3], nums[0] + nums[2])
        dpl = [0] * lea
        dpl[0], dpl[1], dpl[2], dpl[3] = nums[0], nums[1], nums[0] + nums[2], nums[3] + nums[0]
        dpr = [0] * lea
        dpr[0], dpr[1], dpr[2], dpr[3] = nums[0], nums[1], nums[2], nums[3] + nums[1]
        for i in range(4, lea-1):
            dpl[i] = nums[i] + max(dpl[i-2], dpl[i-3])
            dpr[i] = nums[i] + max(dpr[i-2], dpr[i-3])
        dpr[-1] = nums[-1] + max(dpr[-4], dpr[-3])
        return max(dpl[-2], dpl[-3], dpr[-1], dpr[-2])

Another added difference between this and House Robber I is that our base case has expanded from 3 to 4, because this time we are storing dpl[3] as nums[3] + nums[0] and dpr[3] as nums[3] + nums[1] to make sure dpl contains the first element while dpr does not.

Time Complexity: O(N)

Space Complexity: O(N)