Daily LeetCode 213. House Robber II

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

Medium

问题描述

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

思路及代码

这一题是昨天的House Robber的进阶版，昨天的房子排成了一行，今天的房子排成了一圈，触发警报的规则没有变化，因此我们第一个房子和最后一个房子也是相邻的关系，我们只需要在昨天的基础上分别考虑从第一个房子出发和从第二个房子出发两种“抢劫”方式。

我们维护两个数组start_from_first_house和start_from_second_house，需要注意的是，最终比较大小时，考虑start_from_first_house[-2]和start_from_second_house[-1]，因为从一个房子出发不能把最后一个房子算在里面。

代码：

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        if len(nums) < 2: return nums[0]
        
        start_from_first_house = [0] * (len(nums) + 1)
        start_from_second_house = [0] * (len(nums) + 1)

        start_from_first_house[1] = nums[0]

        for i in range(2, len(nums) + 1):
            start_from_first_house[i] = max(start_from_first_house[i - 1], start_from_first_house[i - 2] + nums[i - 1])
            start_from_second_house[i] = max(start_from_second_house[i - 1], start_from_second_house[i - 2] + nums[i - 1])

        return max(start_from_first_house[-2], start_from_second_house[-1])