0%

213. House Robber II

Posted on Edited on In

Solutions: This problem(link) generates from the House Robber. Houses in this problem are not at a straight line but a cycle which means you can not rob both the first and the last house at the same time. To solve this trap we can divide the problem into two subproblems. 1. Compute the optimal value for house[0 : n-1]. 2. Compute the optimal value for house[1 : n]. The maximum value of these two is the final answer for this problem.

# Bottom-Up

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        memo = [-1 for x in range(len(nums))]
        res1, res2 = 0, 0
        memo[0] = nums[0]
        if len(nums) == 1:
            return memo[0]
        memo[1] = max(nums[0], nums[1])
        if len(nums) == 2:
            return memo[1]
        
        for i in range(2, len(nums)-1):
            memo[i] = max(memo[i-2]+nums[i], memo[i-1])
        # Value 1
        res1 = memo[len(nums)-2]
        
        memo[1] = nums[1]
        memo[0] = 0
        for i in range(2, len(nums)):
            memo[i] = max(memo[i-2]+nums[i], memo[i-1])
        # Value 2
        res2 = memo[len(nums)-1]
        return max(res1, res2)

​