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

Question Name: House Robber II

This is a variant of House Robber. We need to apply the previous solution to two sub-arrays and return the maximum of the two results:

1. Do not use the first element, and we can safely consider (may or may not use) the last element (case #1);

2. Oppositely, consider (may or may not use) the first element, and ignore the last element. If the first item was used (case #2a), it is reasonable to ignore the last item. Otherwise (case #2b), case #2b and case #1 share the same leading elements. But case #1 has one more element at the end, therefore case #1 always has an equal-or-larger result.

Totally we need the max(case #1, case #2a, case #2b) = max(case #1, case #2).

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 | class Solution(object): # @param {integer[]} nums # @return {integer} def rob_helper(self, nums): if len(nums) == 0: return 0 if len(nums) <= 2: return max(nums) max_money = [0] * len(nums) max_money[0] = nums[0] max_money[1] = max(nums[0], nums[1]) for house in xrange(2, len(nums)): max_money[house] = max(max_money[house-1], max_money[house-2]+nums[house]) return max_money[-1] def rob(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) == 0: return 0 if len(nums) <= 3: return max(nums) return max(self.rob_helper(nums[1:]), self.rob_helper(nums[:-1])) |

Just want to stop by and say hi ^_^

Hello, welcome back :—-)