每日一题 213. 打家劫舍 II

难度：中等

思路：

1. 首先不看成环，只是当作列表，那么对于第 i 间房，到 i 为止的最高偷窃金额为 f(i) = max(f(i - 1), f(i - 2) + nums[i])
2. 分析递推关系
3. 第一点，不管 i - 2 处的房子是否偷窃，i 处的房子都能偷窃，即如果无视 i - 1 处的房子的偷窃情况，那么 i 处的房子必定是要偷窃才能使得到 i 为止的偷窃金额最大
4. 第二点，如果 i - 1 处的房子没有偷窃，i 处的房子才可以偷窃，那么既然 i - 1处的房子没有偷窃，这种情况就和第一点提到的无视 i - 1 处的房子的偷窃情况相符合
5. 第三点，如果 i - 1 处的房子偷窃了，那么 i 处的房子没得选，只能不偷，也就是保持 f(i - 1) 不变
6. 总之只要从第一点和第二点中选择较大的那种情况即可，在代码中只需设 a, b = nums[0], max(nums[0], nums[1])，然后不断地更新a，b的值即可
7. 最后考虑到房子是成环的，所以如果考虑到 nums[0] 偷窃了，那么只需遍历更新到 nums[-2] 即可；如果 nums[0] 禁止偷窃，那么需设 a, b = 0, nums[1]，这时需要遍历整个 nums 数组

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        
        a, b = nums[0], max(nums[0], nums[1])
        for i in range(2, len(nums) - 1):
            a, b = b, max(b, a + nums[i])

        if b >= a + nums[-1]:
            return b
        ans = max(a, b)

        a, b = 0, nums[1]
        for i in range(2, len(nums)):
            a, b = b, max(b, a + nums[i])

        return max(a, b, ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

学习：对于 for 循环的重复部分可以写成函数的形式来调用以简化代码