Solutions

# Like house robber, but we run the algorithm twice: once on the list of houses excluding the last house, and once on the list of houses excluding the first house. This way, we ensure that we never rob both the first and last house, which are adjacent. We then take the maximum of the two results as our final answer.
# dp

# O(n) time, O(n) space
def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    elif len(nums) == 1:
        return nums[0]

    def getmax(nums: list[int]) -> int:
        if not nums:
            return 0
        elif len(nums) == 1:
            return nums[0]

        dp = [0 for _ in range(len(nums))]
        dp[0] = max(0, nums[0])
        dp[1] = max(dp[0], nums[1])

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

        return  dp[-1]

    return max(getmax(nums[0:-1]), getmax(nums[1:]))


def rob(nums: list[int]) -> int:
    if len(nums) == 1:
        return nums[0]

    def dfs(nums: list[int], i: int, cache: dict[int, int]) -> int:
        if i >= len(nums):
            return 0
        if i in cache:
            return cache[i]

        cache[i] = max(nums[i] + dfs(nums, i+2, cache),
                        dfs(nums, i+1, cache))
        return cache[i]

    return max(dfs(nums[0:-1],0,{}), dfs(nums[1:],0,{}))