打家劫舍 -- 动规

打家劫舍 系列

198. 打家劫舍
213. 打家劫舍 II
337. 打家劫舍 III

from typing import Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Rob:
    """
    打家劫舍 系列
    """
    def solution1(self, nums: List[int]) -> int:
        """
        198. 打家劫舍
        https://leetcode.cn/problems/house-robber/
        :param nums:
        :return:
        """
        n = len(nums)
        # 记录 dp[i+1] 和 dp[i+2]
        dp_i_1 = 0
        dp_i_2 = 0
        # 记录 dp[i]  从第 i 间房子开始抢劫，最多能抢到的钱为 x
        dp_i = 0
        for i in range(n - 1, -1, -1):
            dp_i = max(dp_i_1, nums[i] + dp_i_2)
            dp_i_2 = dp_i_1
            dp_i_1 = dp_i
        return dp_i

    def solution2(self, nums: List[int]) -> int:
        """
        213. 打家劫舍 II
        首先，首尾房间不能同时被抢，那么只可能有三种不同情况：
        要么都不被抢；
        要么第一间房子被抢最后一间不抢；
        要么最后一间房子被抢第一间不抢。
        其实只要比较情况二和情况三就行了。
        https://leetcode.cn/problems/house-robber-ii/
        :param nums: 
        :return: 
        """
        n = len(nums)
        if n == 1:
            return nums[0]
        return max(self.rob_range(nums, 0, n - 2),
                   self.rob_range(nums, 1, n - 1))

    # 仅计算闭区间 [start,end] 的最优结果
    def rob_range(self, nums: List[int], start: int, end: int) -> int:
        dp_i_1 = 0
        dp_i_2 = 0
        dp_i = 0
        for i in range(end, start - 1, -1):
            dp_i = max(dp_i_1, nums[i] + dp_i_2)
            dp_i_2 = dp_i_1
            dp_i_1 = dp_i
        return dp_i

    def solution3(self, root: Optional[TreeNode]) -> int:
        """
        337. 打家劫舍 III
        https://leetcode.cn/problems/house-robber-iii/
        :param nums:
        :return:
        """
        res = self.dp(root)
        return max(res[0], res[1])

    # 返回一个大小为 2 的数组 arr
    # arr[0] 表示不抢 root 的话，得到的最大钱数
    # arr[1] 表示抢 root 的话，得到的最大钱数
    def dp(self, root: TreeNode) -> List[int]:
        if root is None:
            return [0, 0]
        left = self.dp(root.left)
        right = self.dp(root.right)
        # 抢，下家就不能抢了
        rob = root.val + left[0] + right[0]
        # 不抢，下家可抢可不抢，取决于收益大小
        not_rob = max(left[0], left[1]) + max(right[0], right[1])
        return [not_rob, rob]



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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87