Fork me on GitHub

House Robber II

Posted on

Description

https://leetcode.com/problems/house-robber-ii/description/

Solution

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
26
27
28
29
class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ##Divide into two cases
        if nums is None or len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        
        
        value1 = self.rob_range(nums, 0, len(nums) - 2)
        value2 = self.rob_range(nums, 1, len(nums) - 1)
        
        return max(value1, value2)
        
    def rob_range(self, nums, start, end):
        if end - start == 0:
            return nums[start]
        
        dp = [0 for i in range(len(nums))]
        dp[start] = nums[start]
        dp[start + 1] = max(nums[start + 1], dp[start])
        for i in range(start + 2, end + 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i] )
        
        return dp[end]