leetcode-python/dynamic-programming/house_robber_ii.py at master · joshydavid/leetcode-python · GitHub

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
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
    def rob(self, nums):
        n = len(nums)
        if n == 0:
            return 0

        if n == 1:
            return nums[0]

        """
        [2, 4, 6, 8, 10] -> [2, 4, 6, 8]: include first house, MUST exclude last house.
        [2, 4, 6, 8, 10] -> [4, 6, 8, 10]: exclude first house, free to rob or not rob the last house.

        [2,3,2] -> 3
        [1,2,3,1] -> (1 + 3) or (2 + 1)
        either nums[:-1] or nums[1:]
        """

        exclude_last = self._rob_linear(nums[:-1])
        exclude_first = self._rob_linear(nums[1:])

        return max(exclude_last, exclude_first)

    def _rob_linear(self, nums):
        n = len(nums)
        if n == 0:
            return 0

        if n == 1:
            return nums[0]

        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

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

        return dp[-1]

        # Time Complexity: O(n)
        # Space Complexity: O(n)