213.打家劫舍II

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def rob(self, nums: List[int]) -> int:
        # 在 198. 打家劫舍 基础上，把线性变成了环。
        # “环问题”：分情况考虑可以变为 “线性问题”；
        #  a b c d e f     
        #  ---------     情况一：考虑范围不包括尾节点；
        #  a b c d e f 
        #    ---------   情况二：考虑范围不包括头节点。
        # 两种线性情况中的最大值，就是环形情况的最大值。
        # 我们可以直接把 198. 打家劫舍 封装为一个方法，两种情况调用取最大值即可。
        def func_inner(nums: List[int]) -> int:
            d = [0 for _ in range(len(nums))]
            if len(nums)==1: return nums[0]
            elif len(nums)==2: return max(nums[0],nums[1])
            d[0],d[1] = nums[0],max(nums[0],nums[1])
            for i in range(2,len(nums)):
                d[i] = max(d[i-2]+nums[i],d[i-1])
                # print(d)
            return d[len(nums)-1]
        
        if len(nums)==1: return nums[0]
        nums1,nums2 = nums[:-1],nums[1:]
        return max(func_inner(nums1),func_inner(nums2))