Leetcode 213. House Robber II (Python)

Related Topic

Dynamic-Programming.

Description

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.

Sample I/O

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.

Methodology

This question solved by Dynamic Programming. It is similar with question 198 House Robber I.

The difference is ‘All houses at this place are arranged in a circle’.

That means the robber can either rob the first house or last house but not both. So we will give the two input list. One with first house and without the last house. The other one with last house and without the first house. Then we compare the two input list results.

I just slightly modify my previous code to match this need.

Code

def rob(self, nums: List[int]) -> int:
        if not nums: return 0
        def max_money(nums):
            nums = [0]+nums
            for i in range(3,len(nums)):
                nums[i]+=max(nums[i-3],nums[i-2])
            return max(nums[-1],nums[-2])
        return max(max_money(nums[1:]),max_money(nums[:-1])) if len(nums) > 2 else max(nums)

BigO

We iterate all dp array, it will cost O(n), we have to input list, that give n+n cost. Therefore, it is O(n)